{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Apply Operations to Maximize Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #math #number-theory #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #数学 #数论 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #操作使得分最大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;的正整数数组&nbsp;<code>nums</code>&nbsp;和一个整数 <code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>一开始，你的分数为 <code>1</code>&nbsp;。你可以进行以下操作至多 <code>k</code>&nbsp;次，目标是使你的分数最大：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择一个之前没有选过的 <strong>非空</strong>&nbsp;子数组&nbsp;<code>nums[l, ..., r]</code>&nbsp;。</li>\n",
    "\t<li>从&nbsp;<code>nums[l, ..., r]</code>&nbsp;里面选择一个 <strong>质数分数</strong>&nbsp;最高的元素 <code>x</code>&nbsp;。如果多个元素质数分数相同且最高，选择下标最小的一个。</li>\n",
    "\t<li>将你的分数乘以&nbsp;<code>x</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p><code>nums[l, ..., r]</code>&nbsp;表示&nbsp;<code>nums</code>&nbsp;中起始下标为&nbsp;<code>l</code>&nbsp;，结束下标为 <code>r</code>&nbsp;的子数组，两个端点都包含。</p>\n",
    "\n",
    "<p>一个整数的 <strong>质数分数</strong>&nbsp;等于&nbsp;<code>x</code>&nbsp;不同质因子的数目。比方说，&nbsp;<code>300</code>&nbsp;的质数分数为&nbsp;<code>3</code>&nbsp;，因为&nbsp;<code>300 = 2 * 2 * 3 * 5 * 5</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回进行至多 <code>k</code>&nbsp;次操作后，可以得到的 <strong>最大分数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>由于答案可能很大，请你将结果对&nbsp;<code>10<sup>9 </sup>+ 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [8,3,9,3,8], k = 2\n",
    "<b>输出：</b>81\n",
    "<b>解释：</b>进行以下操作可以得到分数 81 ：\n",
    "- 选择子数组 nums[2, ..., 2] 。nums[2] 是子数组中唯一的元素。所以我们将分数乘以 nums[2] ，分数变为 1 * 9 = 9 。\n",
    "- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 1 ，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为 9 * 9 = 81 。\n",
    "81 是可以得到的最高得分。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [19,12,14,6,10,18], k = 3\n",
    "<b>输出：</b>4788\n",
    "<b>解释：</b>进行以下操作可以得到分数 4788 ：\n",
    "- 选择子数组 nums[0, ..., 0] 。nums[0] 是子数组中唯一的元素。所以我们将分数乘以 nums[0] ，分数变为 1 * 19 = 19 。\n",
    "- 选择子数组 nums[5, ..., 5] 。nums[5] 是子数组中唯一的元素。所以我们将分数乘以 nums[5] ，分数变为 19 * 18 = 342 。\n",
    "- 选择子数组 nums[2, ..., 3] 。nums[2] 和 nums[3] 质数分数都为 2，但是 nums[2] 下标更小。所以我们将分数乘以 nums[2] ，分数变为  342 * 14 = 4788 。\n",
    "4788 是可以得到的最高的分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length == n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= min(n * (n + 1) / 2, 10<sup>9</sup>)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [apply-operations-to-maximize-score](https://leetcode.cn/problems/apply-operations-to-maximize-score/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [apply-operations-to-maximize-score](https://leetcode.cn/problems/apply-operations-to-maximize-score/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,3,9,3,8]\\n2', '[19,12,14,6,10,18]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "lst=[True for i in range(100001)]\n",
    "info=[0]*100001\n",
    "info[1]=0\n",
    "info[2]=0\n",
    "for i in range(2,100001):\n",
    "    if lst[i]:\n",
    "        for j in range(i,100001,i):\n",
    "            lst[j]=False\n",
    "            info[j]+=1\n",
    "            \n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        s=[info[i] for i in nums]\n",
    "        n=len(nums)\n",
    "        left_kind=[0]*n\n",
    "        \n",
    "        stack=[0]\n",
    "        for i in range(1,n):\n",
    "            while stack and s[i]>s[stack[-1]]:\n",
    "                left_kind[stack[-1]]=i-stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        for i in range(n):\n",
    "            if left_kind[i]==0:\n",
    "                left_kind[i]=n-i\n",
    "        #print(left_kind)\n",
    "        right_kind=[0]*n\n",
    "        s=s[::-1]\n",
    "        stack=[0]\n",
    "        for i in range(n):\n",
    "            while stack and s[i]>=s[stack[-1]]:\n",
    "                right_kind[stack[-1]]=i-stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        for i in range(n):\n",
    "            if right_kind[i]==0:\n",
    "                right_kind[i]=n-i\n",
    "        \n",
    "        s=s[::-1]\n",
    "        right_kind=right_kind[::-1]\n",
    "        dic={}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in dic:\n",
    "                dic[nums[i]]=left_kind[i]*right_kind[i]\n",
    "            else:\n",
    "                dic[nums[i]]+=left_kind[i]*right_kind[i]\n",
    "        \n",
    "        e=sorted(list(dic.keys()),reverse=True)\n",
    "        ans=1\n",
    "        cnt=0\n",
    "        for i in e:\n",
    "            if cnt+dic[i]<=k:\n",
    "                ans*=pow(i,dic[i],10**9+7)\n",
    "                cnt+=dic[i]\n",
    "            else:\n",
    "                ans*=pow(i,k-cnt,10**9+7)\n",
    "                cnt=k\n",
    "            if cnt>=k:\n",
    "                break\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def get_score(n):\n",
    "            cnt = 0\n",
    "            if n < 2:\n",
    "                return 0\n",
    "            \n",
    "            if n % 2 == 0:\n",
    "                cnt += 1\n",
    "            while n % 2 == 0:\n",
    "                n = n // 2\n",
    "\n",
    "            for i in range(3, int(n**0.5)+1, 2):\n",
    "                if n % i== 0:\n",
    "                    cnt += 1\n",
    "                while n % i== 0:\n",
    "                    n = n // i\n",
    "\n",
    "            if n > 2:\n",
    "                cnt += 1\n",
    "\n",
    "            return cnt\n",
    "        scores = [get_score(i) for i in nums]\n",
    "        times = []\n",
    "        scores.append(float('inf'))\n",
    "        ans, st = 0, [-1]\n",
    "        for r, x in enumerate(scores):\n",
    "            while len(st) > 1 and scores[st[-1]] < x:\n",
    "                i = st.pop()\n",
    "                times.append((nums[i],(i - st[-1])*(r - i)))\n",
    "            st.append(r)\n",
    "        res = 1\n",
    "        mod = 10**9 + 7\n",
    "        for num, time in sorted(times,reverse=True):\n",
    "            res *= pow(num,min(time,k),mod)\n",
    "            res %= mod\n",
    "            k -= min(time,k)\n",
    "            if k == 0:\n",
    "                break\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        factor = [0] * n \n",
    "        for i, x in enumerate(nums):\n",
    "            for p in range(2, int(math.sqrt(x)) + 2):\n",
    "                if x % p == 0:\n",
    "                    factor[i] += 1\n",
    "                    while x % p == 0:\n",
    "                        x //= p \n",
    "            if x > 1:\n",
    "                factor[i] += 1\n",
    "\n",
    "        index = [i for i in range(n)]\n",
    "        index.sort(key=lambda x : -nums[x])\n",
    "\n",
    "        left = [0] * n \n",
    "        right = [0] * n \n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and factor[st[-1]] < factor[i]:\n",
    "                st.pop()\n",
    "            if not st:\n",
    "                left[i] = -1 \n",
    "            else:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and factor[st[-1]] <= factor[i]:\n",
    "                st.pop()\n",
    "            if not st:\n",
    "                right[i] = n \n",
    "            else:\n",
    "                right[i] = st[-1] \n",
    "            st.append(i)\n",
    "        ans = 1\n",
    "        mod = int(1e9+7)\n",
    "\n",
    "        for i in index:\n",
    "            l = (right[i] - i) * (i - left[i])\n",
    "            \n",
    "            if l > k:\n",
    "                ans = (ans * pow(nums[i], k, mod)) % mod \n",
    "                k = 0\n",
    "            else:\n",
    "                ans = (ans * pow(nums[i], l, mod)) % mod \n",
    "                k -= l \n",
    "            if k <= 0:\n",
    "                break \n",
    "        return ans \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        #离线求质因子数模板\n",
    "        MOD = 10**9+7\n",
    "        MX=max(nums)+1\n",
    "        # MX = 10**5+1 #多+1\n",
    "        omega=[0]*MX\n",
    "        for i in range(2,MX):\n",
    "            if omega[i]==0:  # i是质数\n",
    "                for j in range(i,MX,i):\n",
    "                    omega[j]+=1  # i是j的一个质因子，omega[j]增加一个质因子数\n",
    "        stack=[-1]\n",
    "        ret=[0]*len(nums)\n",
    "        arr=list(map(lambda x:omega[x],nums))\n",
    "        arr.append(inf)\n",
    "        n=len(arr)\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and arr[stack[-1]]<arr[i]:\n",
    "                ans=stack.pop()\n",
    "                #以arr[ans]元素为准（元素下标为ans），其左影响边界l为stack[-1]+1（含），其右影响边界r为i-1（含）\n",
    "                #i-1-stack[-1]-1+1=i-stack[-1]-1就是当前弹出下标ans的影响衍生范围\n",
    "                #以下是“最大矩形”的计算例子\n",
    "                ret[ans]=(ans-stack[-1])*(i-ans) #题目至多k次（实际上只需要知道最大的几个(明显小于等于k个)元素的边界情况），因此可以空间换时间，先把左右边界分别存储起来而不计算\n",
    "            stack.append(i)\n",
    "        res=1\n",
    "        for r,t in sorted(zip(nums,ret),reverse=True):\n",
    "            if t>k:\n",
    "                res=res*int(pow(r,k,MOD))%MOD\n",
    "                break\n",
    "            else:\n",
    "                res=res*int(pow(r,t,MOD))%MOD\n",
    "                k-=t\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        #离线求质因子数模板\n",
    "        MOD = 10**9+7\n",
    "        MX=max(nums)+1\n",
    "        # MX = 10**5+1 #多+1\n",
    "        omega=[0]*MX\n",
    "        for i in range(2,MX):\n",
    "            if omega[i]==0:  # i是质数\n",
    "                for j in range(i,MX,i):\n",
    "                    omega[j]+=1  # i是j的一个质因子，omega[j]增加一个质因子数\n",
    "        stack=[-1]\n",
    "        ret=[0]*len(nums)\n",
    "        arr=list(map(lambda x:omega[x],nums))\n",
    "        arr.append(inf)\n",
    "        n=len(arr)\n",
    "        for i in range(n):\n",
    "            while len(stack)>1 and arr[stack[-1]]<arr[i]:\n",
    "                ans=stack.pop()\n",
    "                #以arr[ans]元素为准（元素下标为ans），其左影响边界l为stack[-1]+1（含），其右影响边界r为i-1（含）\n",
    "                #i-1-stack[-1]-1+1=i-stack[-1]-1就是当前弹出下标ans的影响衍生范围\n",
    "                #以下是“最大矩形”的计算例子\n",
    "                ret[ans]=(ans-stack[-1])*(i-ans) #题目至多k次（实际上只需要知道最大的几个(明显小于等于k个)元素的边界情况），因此可以空间换时间，先把左右边界分别存储起来而不计算，这里直接计算了导致时间拉满\n",
    "            stack.append(i)\n",
    "        res=1\n",
    "        for r,t in sorted(zip(nums,ret),reverse=True):\n",
    "            if t>k:\n",
    "                res=res*int(pow(r,k,MOD))%MOD\n",
    "                break\n",
    "            else:\n",
    "                res=res*int(pow(r,t,MOD))%MOD\n",
    "                k-=t\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        # 计算质因数个数\n",
    "        def cal_pri(n):\n",
    "            s = set() # 存储所有质因数的哈希表\n",
    "            x = n\n",
    "            i = 2\n",
    "            while i*i <= x:\n",
    "                while x%i == 0:\n",
    "                    s.add(i)\n",
    "                    x //= i\n",
    "                i += 1\n",
    "            if x > 1:\n",
    "                s.add(x)\n",
    "            return len(s)\n",
    "\n",
    "        # 快速幂\n",
    "        def fast_pow(x, e):\n",
    "            res = 1\n",
    "            while e:\n",
    "                if e % 2:\n",
    "                    res *= x\n",
    "                    res %= mod\n",
    "                x = x ** 2 % mod\n",
    "                e //= 2\n",
    "            return res\n",
    "\n",
    "        arr = [cal_pri(num) for num in nums]\n",
    "        \n",
    "        # 907.子数组的最小值之和 - 的板子\n",
    "        # 单调栈\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            while monoStack and x > arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            left[i] = i - (monoStack[-1] if monoStack else -1)\n",
    "            monoStack.append(i)\n",
    "        monoStack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while monoStack and arr[i] >= arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            right[i] = (monoStack[-1] if monoStack else n) - i\n",
    "            monoStack.append(i)\n",
    "        ans = 1\n",
    "        \n",
    "        # 处理个数\n",
    "        mod = 1000000007\n",
    "        for x, l, r in sorted(zip(nums, left, right))[::-1]:\n",
    "            if k >= r * l:\n",
    "                ans *= fast_pow(x, l * r)\n",
    "                ans %= mod\n",
    "                k -= r * l\n",
    "            else:\n",
    "                ans *= fast_pow(x, k)\n",
    "                ans %= mod\n",
    "                k = 0\n",
    "            if k == 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        arr = [0] * n \n",
    "        for i in range(n):\n",
    "            x = nums[i] \n",
    "            for d in range(2, int(math.sqrt(x)) + 2):\n",
    "                if x % d == 0:\n",
    "                    arr[i] += 1\n",
    "                    while x % d == 0:\n",
    "                        x //=d \n",
    "            if x > 1:\n",
    "                arr[i] += 1\n",
    "        \n",
    "        st = []\n",
    "        left = [-1] * n \n",
    "        right = [n] * n \n",
    "        for i in range(n):\n",
    "            while st and arr[st[-1]] < arr[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and arr[st[-1]] <= arr[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i] = st[-1] \n",
    "            st.append(i)\n",
    "        \n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda i : nums[i]) \n",
    "        Mod = int(1e9+7)\n",
    "        ans = 1\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            idx = index[i]\n",
    "            p = (right[idx] - idx) * (idx - left[idx]) \n",
    "            if k >= p:\n",
    "                ans = (ans * pow(nums[idx], p, Mod))%Mod \n",
    "                k-=p \n",
    "            else:\n",
    "                ans = (ans * pow(nums[idx], k, Mod))%Mod \n",
    "                break \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "pri = []\n",
    "fac = [0] * (N + 1)\n",
    "score = [0] * (N + 1)\n",
    "for i in range(2, N + 1):\n",
    "    if not fac[i]:\n",
    "        fac[i] = i\n",
    "        pri.append(i)\n",
    "        score[i] = 1\n",
    "    for p in pri:\n",
    "        if i * p > N:\n",
    "            break\n",
    "        fac[i * p] = p\n",
    "        score[i * p] = score[i] + 1\n",
    "        if fac[i] == p:\n",
    "            score[i * p] -= 1\n",
    "            break\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], m: int) -> int:\n",
    "        a = [score[x] for x in nums]\n",
    "        stk = [-1]\n",
    "        cnt = [0] * len(a)\n",
    "        for i, x in enumerate(a + [inf]):\n",
    "            while len(stk) > 1 and a[stk[-1]] < x:\n",
    "                j = stk[-1]\n",
    "                k = stk[-2]\n",
    "                cnt[j] += (j - k) * (i - j)\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        ans = 1\n",
    "        for x, y in sorted(zip(nums, cnt), reverse=True):\n",
    "            t = min(y, m)\n",
    "            m -= t\n",
    "            ans *= pow(x, t, MOD)\n",
    "            ans %= MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5 + 5\n",
    "a = [1] * N\n",
    "b = [1] * N\n",
    "f = [0] * N\n",
    "for i in range(2, N):\n",
    "    if a[i]:\n",
    "        for j in range(2 * i, N, i):\n",
    "            a[j] = 0\n",
    "            b[j] = i\n",
    "        b[i] = i\n",
    "    v = i\n",
    "    while b[v] > 1:\n",
    "        f[i] += 1\n",
    "        x = b[v]\n",
    "        while v % x == 0:\n",
    "            v //= x\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, s: List[int], k: int) -> int:\n",
    "        n = len(s)\n",
    "        d = Counter()\n",
    "        t = [f[s[i]] for i in range(n)]\n",
    "        t.append(inf)\n",
    "        l = [0] * n\n",
    "        q = [n]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while t[q[-1]] <= t[i]:\n",
    "                q.pop()\n",
    "            l[i] = q[-1] - i\n",
    "            q.append(i)\n",
    "        q = [-1]\n",
    "        for i in range(n):\n",
    "            while t[q[-1]] < t[i]:\n",
    "                q.pop()\n",
    "            d[s[i]] += l[i] * (i - q[-1])\n",
    "            q.append(i)\n",
    "        ans = sorted(d.items(), reverse = True)\n",
    "        res = 1\n",
    "        m = 10 ** 9 + 7\n",
    "        for a, b in ans:\n",
    "            res *= pow(a, min(k, b), m)\n",
    "            res %= m\n",
    "            k -= b\n",
    "            if k <= 0:\n",
    "                break\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        def prime_score(num):\n",
    "            # if num==1:\n",
    "            #     return 0\n",
    "            score = 0\n",
    "            for i in range(2, int(sqrt(num))+1):\n",
    "                if num==1:\n",
    "                    break\n",
    "                if num%i==0:\n",
    "                    score += 1\n",
    "                    while (num%i==0):\n",
    "                        num /= i\n",
    "            if num!=1:\n",
    "                score += 1\n",
    "            return score\n",
    "\n",
    "        score_lst = list(map(prime_score, nums))\n",
    "        # print(score_lst)\n",
    "\n",
    "        n = len(nums)\n",
    "        left_subs = list(range(n))\n",
    "        right_subs = list(range(n-1, -1, -1))\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and score_lst[st[-1]]<score_lst[i]:\n",
    "                idx = st.pop()\n",
    "                right_subs[idx] = i-idx-1\n",
    "            st.append(i)\n",
    "        # for i in st:\n",
    "        #     right_subs[i] = n-i-1\n",
    "\n",
    "        st.clear()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            # left_sub_num = 0\n",
    "            while st and score_lst[st[-1]]<=score_lst[i]:\n",
    "                idx = st.pop()\n",
    "                left_subs[idx] = idx-i-1\n",
    "            st.append(i)\n",
    "        # for i in st:\n",
    "        #     left_subs[i] = i\n",
    "\n",
    "        subs = [0]*n\n",
    "        for i in range(n):\n",
    "            subs[i] = (right_subs[i]+1)*(left_subs[i]+1)\n",
    "        \n",
    "        # print(left_subs)\n",
    "        # print(right_subs)\n",
    "        # print(subs)\n",
    "        sorted_indices = sorted(range(n), key=lambda x:nums[x], reverse=True)\n",
    "        # print(sorted_indices)\n",
    "\n",
    "        # def pow_mod(base, exponent):\n",
    "        #     # 快速幂算法\n",
    "        #     result = 1\n",
    "        #     while exponent > 0:\n",
    "        #         if exponent % 2 == 1:\n",
    "        #             result = (result * base) % 1000000007\n",
    "        #         base = (base * base) % 1000000007\n",
    "        #         exponent = exponent // 2\n",
    "\n",
    "        #     return result\n",
    "\n",
    "        # print(pow_mod(9, 2))\n",
    "\n",
    "        res = 1\n",
    "        for i in sorted_indices:\n",
    "            if k>=subs[i]:\n",
    "                k -= subs[i]\n",
    "                # res *= (nums[i]**subs[i])%1000000007\n",
    "                res *= pow(nums[i], subs[i], 1000000007)\n",
    "                res %= 1000000007\n",
    "            else:\n",
    "                # res *= (nums[i]**k)%1000000007\n",
    "                res *= pow(nums[i], k, 1000000007)\n",
    "                res %= 1000000007\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        def f(num):\n",
    "            vis = set()\n",
    "            s = num\n",
    "            x = 2\n",
    "            while x * x <= s:\n",
    "                while s % x == 0:\n",
    "                    vis.add(x)\n",
    "                    s //= x\n",
    "                x += 1\n",
    "            if s > 1:\n",
    "                vis.add(s)\n",
    "            return len(vis)\n",
    "\n",
    "        b = [inf] + list(map(f, nums)) + [inf]\n",
    "        st = [0]\n",
    "        # [1,2,2,2,4,3,2]\n",
    "        # 左边找离自己最近的【大于等于】自己的\n",
    "        # 右边找离自己最近的【大于】自己的\n",
    "        q = []\n",
    "        for i, v in enumerate(b):\n",
    "            while st and b[st[-1]] < v:\n",
    "                pos = st.pop()\n",
    "                left = pos - st[-1]\n",
    "                right = i - pos\n",
    "                heappush(q, (-nums[pos - 1], left * right))\n",
    "\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 1\n",
    "        while k > 0:\n",
    "            v, cnt = heappop(q)\n",
    "            v *= -1\n",
    "            real_cnt = min(k, cnt)\n",
    "            k -= real_cnt\n",
    "            ans *= pow(v, real_cnt, mod)\n",
    "            ans %= mod\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxNum = 10 ** 5 + 1\n",
    "primes = [0] * maxNum\n",
    "for i in range(2, maxNum):\n",
    "    if primes[i] == 0:\n",
    "        for x in range(i, maxNum, i):\n",
    "            primes[x] += 1 \n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and primes[nums[stack[-1]]] < primes[nums[i]]:\n",
    "                right[stack.pop()] = i \n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        print(left)\n",
    "        print(right)\n",
    "        res = 1 \n",
    "        mod = 10 ** 9 + 7\n",
    "        for idx in sorted(range(n), key = lambda x: - nums[x]):\n",
    "            cap = min(k, (idx - left[idx]) * (right[idx] - idx))\n",
    "            res = res * pow(nums[idx], cap, mod) % mod\n",
    "            k -= cap \n",
    "            if k == 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 100000\n",
    "f = [0] * (N + 1)\n",
    "minp = list(range(N + 1))\n",
    "prime = []\n",
    "for i in range(2, N + 1):\n",
    "    if minp[i] == i:\n",
    "        f[i] = 1\n",
    "        prime.append(i)\n",
    "    else:\n",
    "        m = minp[i]\n",
    "        i2 = i\n",
    "        while i2 % m == 0: i2 //= m\n",
    "        f[i] = f[i2] + 1\n",
    "    j = 0\n",
    "    while j < len(prime) and i * prime[j] <= N:\n",
    "        minp[i * prime[j]] = min(minp[i * prime[j]], prime[j])\n",
    "        if i % prime[j] == 0:\n",
    "            break\n",
    "        j = j + 1\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        f2 = list(f[a] for a in nums)\n",
    "        L, R = [-1] * len(nums), [len(nums)] * len(nums)\n",
    "        stack = []\n",
    "        for i in range(len(f2)):\n",
    "            while stack and stack[-1][1] < f2[i]: R[stack.pop()[0]] = i\n",
    "            if stack: L[i] = stack[-1][0]\n",
    "            stack.append((i, f2[i]))\n",
    "        indexes = sorted(range(len(nums)), key = lambda x: nums[x], reverse = True)\n",
    "        ans = 1\n",
    "        for i in indexes:\n",
    "            can = min(k, (R[i] - i) * (i - L[i]))\n",
    "            ans *= pow(nums[i], can, 1000000007)\n",
    "            ans %= 1000000007\n",
    "            k -= can\n",
    "            if k == 0: break\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "f = []\n",
    "for x in range(100001):\n",
    "    s = set()\n",
    "    i = 2\n",
    "    while i * i <= x:\n",
    "        if x % i == 0:\n",
    "            s.add(i)\n",
    "            x //= i\n",
    "            while x % i == 0:\n",
    "                x //= i\n",
    "        i += 1\n",
    "    if x > 1:\n",
    "        s.add(x)\n",
    "    f.append(len(s))\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "        st = []\n",
    "        for i,v in enumerate(nums):\n",
    "            while st and f[nums[st[-1]]] < f[v]:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        arr2 = sorted(list(range(n)),key = lambda x:-nums[x])\n",
    "        MOD = int(1e9+7)\n",
    "        ans = 1\n",
    "        for i in arr2:\n",
    "            cnt = (i - left[i]) * (right[i] - i)\n",
    "            ans = ans * pow(nums[i],min(cnt,k),MOD)%MOD\n",
    "            k -= cnt\n",
    "            if k <= 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX = 100001\n",
    "MOD = 1000000007\n",
    "pscore = [0] * MAX\n",
    "for num in range(2, MAX):\n",
    "    if pscore[num] == 0:\n",
    "        for mult in range(num, MAX, num):\n",
    "            pscore[mult] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        count = [1] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and pscore[nums[i]] > pscore[nums[stack[-1]]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                count[i] = i - stack[-1]\n",
    "            else:\n",
    "                count[i] = i + 1\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and pscore[nums[i]] >= pscore[nums[stack[-1]]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                count[i] *= stack[-1] - i\n",
    "            else:\n",
    "                count[i] *= n - i\n",
    "            stack.append(i)\n",
    "        \n",
    "        # print(max(count))\n",
    "        arr = sorted([(num, i) for i, num in enumerate(nums)], reverse=True)\n",
    "        # print(arr)\n",
    "        result = 1\n",
    "        \n",
    "        \n",
    "        i = 0\n",
    "        while k and i < n:\n",
    "            j = arr[i][1]\n",
    "            # print(nums[j], count[j])\n",
    "            m = min(k, count[j])\n",
    "            result = result * pow(nums[j], m, MOD) % MOD\n",
    "            # print(result)\n",
    "            k -= m\n",
    "            count[j] -= m\n",
    "            if count[j] == 0:\n",
    "                i += 1\n",
    "                \n",
    "        return result\n",
    "                \n",
    "                \n",
    "            \n",
    "                \n",
    "                                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxNum = 10 ** 5 + 1\n",
    "primes = [0] * maxNum\n",
    "for p in range(2, maxNum):\n",
    "    if primes[p] == 0:\n",
    "        for x in range(p, maxNum, p):\n",
    "            primes[x] += 1 \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        right = [n] * n \n",
    "        left = [-1] * n \n",
    "        for i in range(n):\n",
    "            while stack and primes[nums[stack[-1]]] < primes[nums[i]]:\n",
    "                right[stack.pop()] = i \n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        res = 1 \n",
    "        mod = 10 ** 9 + 7\n",
    "        for idx in sorted(range(n), key = lambda x: - nums[x]):\n",
    "            cap = min(k, (idx - left[idx]) * (right[idx] - idx))\n",
    "            res = res * pow(nums[idx], cap, mod) % mod \n",
    "            k -= cap \n",
    "            if k == 0:\n",
    "                break \n",
    "        return res \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxNum = 10 ** 5 + 1\n",
    "primes = [0] * maxNum\n",
    "for p in range(2, maxNum):\n",
    "    if primes[p] == 0:\n",
    "        for x in range(p, maxNum, p):\n",
    "            primes[x] += 1 \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        right = [n] * n \n",
    "        left = [-1] * n \n",
    "        for i in range(n):\n",
    "            while stack and primes[nums[stack[-1]]] < primes[nums[i]]:\n",
    "                right[stack.pop()] = i \n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        res = 1 \n",
    "        mod = 10 ** 9 + 7\n",
    "        for idx in sorted(range(n), key = lambda x: - nums[x]):\n",
    "            cap = min(k, (idx - left[idx]) * (right[idx] - idx))\n",
    "            res = res * pow(nums[idx], cap, mod) % mod \n",
    "            k -= cap \n",
    "            if k == 0:\n",
    "                break \n",
    "        return res \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "maxi = 10**5  \n",
    "tab = [0] * (maxi+1)\n",
    "for i in range(2, maxi+1):\n",
    "    if not tab[i]:\n",
    "        for j in range(i, maxi+1, i):\n",
    "            tab[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        scores = [tab[num] for num in nums]\n",
    "        \n",
    "        left = list(range(n))\n",
    "        stack = [0]  \n",
    "        for i in range(1, n):\n",
    "            score = scores[i]\n",
    "            while len(stack)>0 and scores[stack[-1]] < score:\n",
    "                stack.pop()  \n",
    "            if len(stack) == 0:\n",
    "                left[i] = 0  \n",
    "            else:\n",
    "                left[i] = stack[-1] + 1\n",
    "            stack.append(i)  \n",
    "        \n",
    "        stack = [n-1]  \n",
    "        left[n-1] = n-left[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            score = scores[i]\n",
    "            while len(stack)>0 and scores[stack[-1]] <= score:\n",
    "                stack.pop()  \n",
    "            if len(stack) == 0:\n",
    "                r = n-1   \n",
    "            else:\n",
    "                r = stack[-1] - 1  \n",
    "            l = left[i]  \n",
    "            left[i] = (r-i+1)*(i-l+1)\n",
    "            stack.append(i)\n",
    "        \n",
    "        lst = [(num, cnt) for num, cnt in zip(nums, left)]  \n",
    "        lst.sort(key=lambda x: -x[0])  \n",
    "        \n",
    "        i = 0\n",
    "        res = 1\n",
    "        while k > 0:\n",
    "            num = lst[i][0]  \n",
    "            x = min(k, lst[i][1])  \n",
    "            res *= pow(num, x, MOD)\n",
    "            res %= MOD\n",
    "            i += 1\n",
    "            k -= x\n",
    "        \n",
    "        return res \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        @lru_cache\n",
    "        def depose(v):\n",
    "            ans = 0\n",
    "            d = 2\n",
    "            while v >= d ** 2:  # 如果v存在因子，则因子一定是小于d的\n",
    "                if v % d == 0:\n",
    "                    ans += 1\n",
    "                while v % d == 0:\n",
    "                    v //= d\n",
    "                d += 1\n",
    "            \n",
    "            if v > 1: # 还留有一个比d更大的质数的时候\n",
    "                ans += 1\n",
    "            return ans\n",
    "        \n",
    "        score = [depose(v) for v in nums]\n",
    "        mod = 10**9+7\n",
    "\n",
    "        def get_bonder(score, noteq=False):\n",
    "            n = len(score)\n",
    "            st = [] # 单调递减栈， 找 nxt 大元素\n",
    "            ans = [1]*n\n",
    "            for i in range(n):\n",
    "                while st and (score[st[-1]] < score[i] or (noteq and score[st[-1]] == score[i])):\n",
    "                    \n",
    "                    idx = st.pop()\n",
    "                    # print(st, idx, st)\n",
    "                    ans[idx] = i - idx\n",
    "                st.append(i)\n",
    "            \n",
    "            for i in st:\n",
    "                ans[i] = n - i\n",
    "            return ans\n",
    "        \n",
    "        right = get_bonder(score, noteq=False) # right 必须贪心的拿， 区间可以包含相等元素\n",
    "        left = get_bonder(score[::-1], noteq=True)[::-1]   # left 不能贪心的拿\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        # print(score)\n",
    "        # print(nums)\n",
    "\n",
    "        arr = sorted([(nums[i], left[i] * right[i]) for i in range(len(nums))], reverse=True)\n",
    "        ans = 1\n",
    "        p = 0\n",
    "        # print(arr)\n",
    "        while k > 0:\n",
    "            # print(arr[p])\n",
    "            t = min(k, arr[p][1])\n",
    "            ans = pow(arr[p][0], t, mod=mod) * ans % mod\n",
    "            k -= t\n",
    "            p += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_num = 10 ** 5 + 1\n",
    "prime_score = [0] * (max_num+1)\n",
    "# prime_score[1] = 1\n",
    "for i in range(2, max_num):\n",
    "    if prime_score[i] > 0:\n",
    "        continue\n",
    "    num = i\n",
    "    while num < max_num:\n",
    "        prime_score[num] += 1\n",
    "        num += i\n",
    "# print(prime_score)\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        1. 计算质数分数 A[i]\n",
    "\n",
    "        2. 计算第 i 个数最多可以被取多少次. 包含这个的区间要满足：左边的 A[j] 比 A[i] 小，右边的 A[k] <= A[i]\n",
    "            B[i]: 左边 >= A[i] 的 j\n",
    "            C[i]: 右边 > A[i] 的 k\n",
    "        3. 排序后依次取\n",
    "            这里需要写一个带 mod 的乘方\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        def sq(x, y, mod):\n",
    "            if x == 1:\n",
    "                return 1\n",
    "            res = 1\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    res = res * x % mod\n",
    "                x = x * x % mod\n",
    "                y = y // 2\n",
    "            return int(res)\n",
    "\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "\n",
    "\n",
    "        A = []\n",
    "        for num in nums:\n",
    "            A.append(prime_score[num])\n",
    "        B = [-1] * n\n",
    "        sB = []\n",
    "        C = [n] * n\n",
    "        for idx, num in enumerate(A):\n",
    "            while sB and sB[-1][0] < num:\n",
    "                middle = sB.pop()\n",
    "                C[middle[1]] = idx\n",
    "            if sB:\n",
    "                B[idx] = sB[-1][1]\n",
    "            sB.append((num, idx))\n",
    "        D = []\n",
    "        for idx in range(n):\n",
    "            left = idx - B[idx]\n",
    "            right = C[idx] - idx\n",
    "            D.append((nums[idx], left * right))\n",
    "        ans = 1\n",
    "        D = sorted(D, reverse = True)\n",
    "        p = 0\n",
    "        while k > 0:\n",
    "            if D[p][1] < k:\n",
    "                ans *= int(sq(D[p][0], D[p][1], MOD))\n",
    "                ans = ans % MOD\n",
    "                k -= D[p][1]\n",
    "                p += 1\n",
    "            else:\n",
    "                ans *= int(sq(D[p][0], k, MOD))\n",
    "                ans = ans % MOD\n",
    "                break\n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fac = [0] * (10 ** 5 + 1)\n",
    "for i in range(2, 10 ** 5 + 1):\n",
    "    if fac[i] > 0: continue\n",
    "    for j in range(i, 10 ** 5 + 1, i):\n",
    "        fac[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        ss = []\n",
    "        for num in nums:\n",
    "            ss.append(fac[num])\n",
    "\n",
    "        n = len(nums)\n",
    "        rights = [0] * n\n",
    "        st = deque()\n",
    "        for i in range(n):\n",
    "            e = ss[i]\n",
    "            while st and e > st[-1][0]:\n",
    "                _, j = st.pop()\n",
    "                rights[j] = i - j\n",
    "            st.append((e, i))\n",
    "        else:\n",
    "            while st:\n",
    "                _, j = st.pop()\n",
    "                rights[j] = n - j\n",
    "        \n",
    "        lefts = [0] * n\n",
    "        st = deque()\n",
    "        for i in reversed(range(n)):\n",
    "            e = ss[i]\n",
    "            while st and e >= st[-1][0]:\n",
    "                _, j = st.pop()\n",
    "                lefts[j] = j - i\n",
    "            st.append((e, i))\n",
    "        else:\n",
    "            while st:\n",
    "                _, j = st.pop()\n",
    "                lefts[j] = j + 1\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        arr = sorted([(num, i) for i, num in enumerate(nums)], reverse = True)\n",
    "        j, res = 0, 1\n",
    "        for num, i in arr:\n",
    "            if k <= 0: break\n",
    "            pp = rights[i] * lefts[i]\n",
    "            p = min(k, pp)\n",
    "            res = (res * pow(num, p, mod)) % mod\n",
    "            k -= pp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primes = []\n",
    "def calc(maxN):\n",
    "    vis = [False] * (maxN + 1)\n",
    "    for i in range(2, maxN + 1):\n",
    "        if not vis[i]:\n",
    "            primes.append(i)\n",
    "        for p in primes:\n",
    "            if i * p > maxN:\n",
    "                break\n",
    "            vis[i * p] = True\n",
    "            if i % p == 0:\n",
    "                break\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        if not primes:\n",
    "            calc(10 ** 5)\n",
    "        scores = []\n",
    "        for x in nums:\n",
    "            tmp = x\n",
    "            cnt = 0\n",
    "            for p in primes:\n",
    "                if p * p > tmp:\n",
    "                    break\n",
    "                if tmp % p == 0:\n",
    "                    cnt += 1\n",
    "                    while tmp % p == 0:\n",
    "                        tmp //= p\n",
    "            if tmp > 1:\n",
    "                cnt += 1\n",
    "            scores.append(cnt)\n",
    "        n = len(nums)\n",
    "        st = []\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        for i in range(n):\n",
    "            while st and scores[st[-1]] < scores[i]:\n",
    "                right[st[-1]] = i\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        res = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        cans = []\n",
    "        for i in range(n):\n",
    "            cans.append((-nums[i], (i - left[i]) * (right[i] - i)))\n",
    "        cans.sort()\n",
    "        for i in range(n):\n",
    "            res = res * pow(-cans[i][0], min(k, cans[i][1]), mod) % mod\n",
    "            if cans[i][1] >= k:\n",
    "                break\n",
    "            k -= cans[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAXN = 100001\n",
    "\n",
    "prims = []\n",
    "is_prim = [True] * MAXN\n",
    "prim_count = [1] * MAXN\n",
    "min_prim = [None] * MAXN\n",
    "next_prim = [None] * MAXN\n",
    "\n",
    "prim_count[1] = 0\n",
    "\n",
    "for i in range(2, MAXN):\n",
    "    if is_prim[i]:\n",
    "        prims.append(i)\n",
    "        min_prim[i] = i\n",
    "        next_prim[i] = 1\n",
    "    for p in prims:\n",
    "        if p > min_prim[i]:\n",
    "            break\n",
    "        v = p * i\n",
    "        if v >= MAXN:\n",
    "            break\n",
    "        is_prim[v] = False\n",
    "        min_prim[v] = p\n",
    "        if p == min_prim[i]:\n",
    "            prim_count[v] = prim_count[i]\n",
    "            next_prim[v] = next_prim[i]\n",
    "        else:\n",
    "            prim_count[v] = prim_count[i] + 1\n",
    "            next_prim[v] = i\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        rank = [prim_count[i] for i in nums]\n",
    "        stack = [(-1, 100001)]\n",
    "        left_most = [None] * N\n",
    "        right_most = [None] * N\n",
    "        for i, v in enumerate(rank):\n",
    "            while stack[-1][1] < v:\n",
    "                j, _ = stack.pop()\n",
    "                right_most[j] = i\n",
    "            left_most[i] = stack[-1][0]\n",
    "            stack.append((i, v))\n",
    "        while stack:\n",
    "            j, _ = stack.pop()\n",
    "            right_most[j] = N\n",
    "        indices = sorted(range(N), key=lambda x: nums[x], reverse=True)\n",
    "        ans = 1\n",
    "        for i in indices:\n",
    "            limit = (right_most[i] - i) * (i - left_most[i])\n",
    "            c = min(limit, k)\n",
    "            ans = (ans * pow(nums[i], c, 1000000007)) % 1000000007\n",
    "            k -= c\n",
    "            if not k:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def primefilter():\n",
    "    ret = [None]*100001\n",
    "    for i in range(2,len(ret)):\n",
    "        if ret[i]==None:\n",
    "            #i是质数\n",
    "            for j in range(i,len(ret),i):\n",
    "                if ret[j]==None:\n",
    "                    ret[j] = i\n",
    "    return ret\n",
    "\n",
    "def count(num,parr):\n",
    "    ret = 0\n",
    "    prev = None\n",
    "    while num!=1:\n",
    "        if parr[num]!=prev:\n",
    "            ret += 1\n",
    "            prev = parr[num]\n",
    "        num //= parr[num]\n",
    "    return ret\n",
    "\n",
    "def powfunc(base,n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    sh,remainder = divmod(n,2)\n",
    "    tmp = powfunc(base,sh)\n",
    "    ret = tmp*tmp%1000000007\n",
    "    if remainder==1:\n",
    "        ret = ret*base%1000000007\n",
    "    return ret\n",
    "\n",
    "parr = primefilter()\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        carr = []\n",
    "        for i in range(len(nums)):\n",
    "            carr.append(count(nums[i],parr))\n",
    "        #print(carr)\n",
    "        #对carr实时正反序单调栈\n",
    "        lb = [] #左边界，到左边第一个大于等于的停止\n",
    "        rb = [None]*len(carr) #右边界，到左边第一个大于的停止\n",
    "        stack = []\n",
    "        for i in range(len(carr)):\n",
    "            while len(stack)!=0:\n",
    "                if stack[-1][0]<carr[i]:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    lb.append(stack[-1][1]+1)\n",
    "                    stack.append([carr[i],i])\n",
    "                    break\n",
    "            else:\n",
    "                lb.append(0)\n",
    "                stack.append([carr[i],i])\n",
    "        #print(lb)\n",
    "        stack = []\n",
    "        for i in range(len(carr)-1,-1,-1):\n",
    "            while len(stack)!=0:\n",
    "                if stack[-1][0]<=carr[i]:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    rb[i] = stack[-1][1]-1\n",
    "                    stack.append([carr[i],i])\n",
    "                    break\n",
    "            else:\n",
    "                rb[i] = len(carr)-1\n",
    "                stack.append([carr[i],i])\n",
    "        #print(rb)\n",
    "        \n",
    "        d = {}\n",
    "        for i in range(len(nums)):\n",
    "            d[nums[i]] = d.get(nums[i],0) + (i-lb[i]+1)*(rb[i]-i+1)%1000000007\n",
    "        #print(d)\n",
    "\n",
    "        darr = []\n",
    "        for kk,v in d.items():\n",
    "            darr.append([kk,v])\n",
    "        \n",
    "        darr.sort(reverse=True)\n",
    "        #print(darr)\n",
    "\n",
    "        ret = 1\n",
    "        for kv in darr:\n",
    "            if k>kv[1]:\n",
    "                ret *= powfunc(kv[0],kv[1])\n",
    "                ret %= 1000000007\n",
    "                k -= kv[1]\n",
    "            else:\n",
    "                ret *= powfunc(kv[0],k)\n",
    "                ret %= 1000000007\n",
    "                break\n",
    "        \n",
    "        return ret\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxi = 10 ** 5\n",
    "score = [0] * (maxi + 1)\n",
    "for i in range(2, maxi + 1):\n",
    "    if not score[i]:\n",
    "        for j in range(i, maxi + 1, i):\n",
    "            score[j] += 1\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        note = [score[x] for x in nums] # 不一定要创建数组，可以直接在后面调用的时候去查；这里为了更直观地展示\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 单调栈可以设定一个哨兵元素\n",
    "        left = [None] * n\n",
    "        stack = [(-1, inf)]\n",
    "        for i in range(n):\n",
    "            while stack[-1][1] < note[i]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1][0]\n",
    "            stack.append((i, note[i]))\n",
    "        \n",
    "        right = [None] * n\n",
    "        stack = [(n, inf)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack[-1][1] <= note[i]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1][0]\n",
    "            stack.append((i, note[i]))\n",
    "\n",
    "        counts = [(right[i] - i) * (i - left[i]) for i in range(n)]\n",
    "        ans = 1\n",
    "        for i in sorted(range(n), key=lambda x: -nums[x]):\n",
    "            if k < counts[i]:\n",
    "                ans *= pow(nums[i], k, mod)\n",
    "                ans %= mod\n",
    "                break\n",
    "            else:\n",
    "                ans *= pow(nums[i], counts[i], mod)\n",
    "                ans %= mod\n",
    "                k -= counts[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 100010\n",
    "MOD = 10 ** 9 + 7\n",
    "P = [0] * MX\n",
    "for i in range(2, MX):\n",
    "    if P[i] == 0:\n",
    "        for j in range(i, MX, i):\n",
    "            P[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and P[nums[st[-1]]] < P[x]:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 1\n",
    "        for x, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            t = (i - left[i]) * (right[i] - i)\n",
    "            if t >= k:\n",
    "                return ans * pow(x, k, MOD) % MOD\n",
    "            ans = ans * pow(x, t, MOD) % MOD\n",
    "            k -= t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "MX = 10 ** 5 + 1\n",
    "cnt=[0]*MX\n",
    "for i in range(2,MX):\n",
    "    if cnt[i]==0:\n",
    "        for j in range(i,MX,i):\n",
    "            cnt[j] +=1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n=len(nums)\n",
    "       \n",
    "        amnt=[0]*n\n",
    "        for i,v in enumerate(nums):\n",
    "            amnt[i]=cnt[v] \n",
    "        \n",
    "      \n",
    "        l=[-1]*n\n",
    "        r=[n]*n\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            while stack and amnt[i]>amnt[stack[-1]]:\n",
    "                r[stack[-1]]=i\n",
    "                stack.pop()\n",
    "            if len(stack):\n",
    "                l[i]=stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        #print(l)\n",
    "        #print(r)\n",
    "        tot=[0]*n\n",
    "        for i in range(n):\n",
    "            tot[i]=(i-l[i])*(r[i]-i)\n",
    "        \n",
    "        #print(tot)\n",
    "        #arr=sorted(zip(nums,tot),reverse=True)\n",
    "        arr=sorted(range(n),key=lambda x: -nums[x])\n",
    "                  \n",
    "        def multi(x,y,n):\n",
    "            ans = 0\n",
    "            ans=x%n\n",
    "            ans=ans*(y%n)%n\n",
    "            return ans\n",
    "\n",
    "        def multimod(x,y,mod):\n",
    "            ans=1\n",
    "            while(y!=0):  \n",
    "                if y%2:         #奇数\n",
    "                    ans=multi(ans,x,mod)\n",
    "                x=multi(x,x,mod)\n",
    "                y=y//2          #整除2\n",
    "            return ans\n",
    "\n",
    "        \n",
    "        res=1\n",
    "        '''\n",
    "        for a,b in arr:\n",
    "            if b>=k:\n",
    "                res =multi(res,multimod(a,k,MOD),MOD)\n",
    "                break\n",
    "            else:\n",
    "                res =multi(res,multimod(a,b,MOD),MOD)\n",
    "                k -=b\n",
    "        '''\n",
    "        for i in arr:\n",
    "            a,b=nums[i],tot[i]\n",
    "            if b>=k:\n",
    "                res =res*pow(a,k,MOD)%MOD\n",
    "                break\n",
    "            else:\n",
    "                res =res*pow(a,b,MOD)%MOD\n",
    "                k -=b\n",
    "        \n",
    "        return res  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primeCount = [0]*100001\n",
    "for i in range(2, 100001):\n",
    "    if not primeCount[i]:\n",
    "        for j in range(i, 100001, i):\n",
    "            primeCount[j] += 1\n",
    "\n",
    "mod = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # print(self.primeCount[:20])\n",
    "\n",
    "        n = len(nums)\n",
    "        leftBound = [-1] * n\n",
    "        rightBound = [n] * n\n",
    "        stack = []\n",
    "        for index in range(n):\n",
    "            while len(stack) and primeCount[nums[stack[-1]]] < primeCount[nums[index]]:\n",
    "                t = stack.pop()\n",
    "                rightBound[t] = index\n",
    "            if stack:\n",
    "                leftBound[index] = stack[-1]\n",
    "            stack.append(index)\n",
    "\n",
    "        ans = 1\n",
    "        for num, index in sorted([(nums[i], i) for i in range(n)], reverse=True):\n",
    "            cnt = (index-leftBound[index])*(rightBound[index]-index)\n",
    "\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            if cnt >= k:\n",
    "                ans = ans*pow(num, k, mod) % mod\n",
    "                break\n",
    "            else:\n",
    "                ans = ans*pow(num, cnt, mod) % mod\n",
    "            k -= cnt\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primeCount = [0]*100001\n",
    "for i in range(2, 100001):\n",
    "    if not primeCount[i]:\n",
    "        for j in range(i, 100001, i):\n",
    "            primeCount[j] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # print(self.primeCount[:20])\n",
    "\n",
    "        leftBound = [-1] * len(nums)\n",
    "        rightBound = [len(nums)] * len(nums)\n",
    "        stack = []\n",
    "        for index in range(len(nums)):\n",
    "            while len(stack) and primeCount[nums[stack[-1]]] < primeCount[nums[index]]:\n",
    "                t = stack.pop()\n",
    "                rightBound[t] = index\n",
    "            if stack:\n",
    "                leftBound[index] = stack[-1]\n",
    "            stack.append(index)\n",
    "\n",
    "        array = sorted([(nums[i], i) for i in range(len(nums))], reverse=True)\n",
    "        ans = 1\n",
    "        for num, index in array:\n",
    "            cnt = min(k, (index-leftBound[index])*(rightBound[index]-index))\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            ans = ans*pow(num, cnt, 1000000007) % 1000000007\n",
    "            k -= cnt\n",
    "            if not k: break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums, k: int):\n",
    "        A=10**9+7\n",
    "        def pow(a,b):\n",
    "            ans=1\n",
    "            b=bin(b)\n",
    "            b=list(b[2:])\n",
    "            l=[a]\n",
    "            for i in range(len(b)-1):\n",
    "                l.append((l[-1]*l[-1])%(A))\n",
    "            for i in range(len(b)-1,-1,-1):\n",
    "                if b[i]=='1':\n",
    "                    ans=(ans*l[len(b)-i-1])%(A)\n",
    "            return ans\n",
    "                \n",
    "            \n",
    "        \n",
    "        c=list()\n",
    "        for i in range(2,317):\n",
    "            flag=0\n",
    "            for j in c:\n",
    "                if j*j>i:\n",
    "                    break\n",
    "                if i //j *j==i and j!=1:\n",
    "                    flag=1\n",
    "                    break\n",
    "            if flag==0:\n",
    "                c.append(i)\n",
    "        count=list()\n",
    "        for i in range(len(nums)):\n",
    "            n=nums[i]\n",
    "            cnt=0\n",
    "            for num in c:\n",
    "                if n==1:\n",
    "                    break\n",
    "                if nums[i]%num==0:\n",
    "                    while n%num==0:\n",
    "                        n=n//num\n",
    "                    cnt+=1\n",
    "            if n!=1:\n",
    "                cnt+=1\n",
    "            count.append(cnt)\n",
    "        left=[0]*len(nums)\n",
    "        right=[0]*len(nums)\n",
    "        utime=list()\n",
    "        stack=list()\n",
    "        for i in range(len(nums)):\n",
    "            while len(stack)!=0 and stack[-1][0]<count[i]:\n",
    "                lastname,lasttime=stack.pop()\n",
    "                right[lasttime]=i-lasttime\n",
    "            stack.append((count[i],i))\n",
    "        while len(stack)!=0 :\n",
    "            lastname,lasttime=stack.pop()\n",
    "            right[lasttime]=len(nums)-lasttime\n",
    "\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            while len(stack)!=0 and stack[-1][0]<=count[i]:\n",
    "                lastname,lasttime=stack.pop()\n",
    "                left[lasttime]=lasttime-i\n",
    "            stack.append((count[i],i))\n",
    "        while len(stack)!=0 :\n",
    "            lastname,lasttime=stack.pop()\n",
    "            left[lasttime]=lasttime+1\n",
    "        for i in range(len(nums)):\n",
    "            utime.append((nums[i],right[i]*left[i]))\n",
    "        utime.sort(key=lambda x :-x[0])\n",
    "        ans=1\n",
    "        i=0\n",
    "        while k>0:\n",
    "            if k>utime[i][1]:\n",
    "                k-=utime[i][1]\n",
    "                ans=ans*(pow(utime[i][0],utime[i][1])%(A))%(A)\n",
    "                i+=1\n",
    "            else:\n",
    "                ans=ans*(pow(utime[i][0],k)%(A))%(A)\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "N = 10 ** 5\n",
    "isPrime = [True] * (N + 1)\n",
    "Prime = []\n",
    "for i in range(2, N + 1):\n",
    "    if isPrime[i]:\n",
    "        Prime.append(i)\n",
    "    for p in Prime:\n",
    "        if i * p > N:\n",
    "            break\n",
    "        isPrime[i * p] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "def count(n):\n",
    "    ans = 0\n",
    "    for p in Prime:\n",
    "        if p * p > n:\n",
    "            break\n",
    "        if n % p == 0:\n",
    "            ans += 1\n",
    "            while n % p == 0:\n",
    "                n //= p\n",
    "    if n > 1:\n",
    "        ans += 1\n",
    "    return ans\n",
    "\n",
    "def myPow(x, n, mod):\n",
    "    ans = 1\n",
    "    tmp = x\n",
    "    while n > 0:\n",
    "        if n & 1:\n",
    "            ans = (ans * tmp) % mod\n",
    "        tmp = (tmp * tmp) % mod\n",
    "        n //= 2\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        score = [count(i) for i in nums]\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            while tmp and score[tmp[-1]] < score[i]:\n",
    "                right[tmp[-1]] = i\n",
    "                tmp.pop()\n",
    "            if tmp:\n",
    "                left[i] = tmp[-1]\n",
    "            tmp.append(i)\n",
    "        tmp = [(j, i) for i, j in enumerate(nums)]\n",
    "        tmp.sort(reverse = True)\n",
    "        no = k\n",
    "        ans = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        for j, i in tmp:\n",
    "            if no <= 0:\n",
    "                break\n",
    "            tmpi = min(no, (i - left[i]) * (right[i] - i))\n",
    "            ans *= pow(j, tmpi, mod)\n",
    "            ans %= mod\n",
    "            no -= tmpi\n",
    "        return ans         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primeCount = [0]*100001\n",
    "for i in range(2, 100001):\n",
    "    if not primeCount[i]:\n",
    "        for j in range(i, 100001, i):\n",
    "            primeCount[j] += 1\n",
    "\n",
    "mod = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # print(self.primeCount[:20])\n",
    "\n",
    "        n = len(nums)\n",
    "        leftBound = [-1] * n\n",
    "        rightBound = [n] * n\n",
    "        stack = []\n",
    "        for index in range(n):\n",
    "            while len(stack) and primeCount[nums[stack[-1]]] < primeCount[nums[index]]:\n",
    "                t = stack.pop()\n",
    "                rightBound[t] = index\n",
    "            if stack:\n",
    "                leftBound[index] = stack[-1]\n",
    "            stack.append(index)\n",
    "\n",
    "        ans = 1\n",
    "        for num, index, left, right in sorted(zip(nums, range(n), leftBound, rightBound), reverse=True):\n",
    "            cnt = (index-left)*(right-index)\n",
    "\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            if cnt >= k:\n",
    "                ans = ans*pow(num, k, mod) % mod\n",
    "                break\n",
    "            else:\n",
    "                ans = ans*pow(num, cnt, mod) % mod\n",
    "            k -= cnt\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MXN = 10 ** 5 + 1\n",
    "beta = [0] * MXN # 预处理质数分数\n",
    "is_prime = [True] * MXN # 质数\n",
    "\n",
    "# for i in range(2, MXN):\n",
    "#     for j in range(2, isqrt(i) + 1):\n",
    "#         if i % j == 0:\n",
    "#             is_prime[i] = False\n",
    "#             break\n",
    "\n",
    "# for i in range(1, MXN):\n",
    "#     if is_prime[i]:\n",
    "#         beta[i] = 1\n",
    "#         continue\n",
    "    \n",
    "#     c = 0\n",
    "#     x = i\n",
    "#     for p in (2, 3, 5):\n",
    "#         if x % p == 0:\n",
    "#             c += 1\n",
    "#             x //= p\n",
    "#             while x % p == 0:\n",
    "#                 x //= p\n",
    "#     beta[i] = c\n",
    "\n",
    "for i in range(2, MXN):\n",
    "    if beta[i] == 0:\n",
    "        for j in range(i, MXN, i):\n",
    "            beta[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        #我的想法：\n",
    "        # 贪心: 对最大元素所在的子数组贪心，如果最大元素一直是质数分数最高则必贪，否则查看第二大元素是否满足\n",
    "\n",
    "\n",
    "        # 灵神思路：\n",
    "        # 对最大元素所在的子数组贪心： 用单调栈求出能使得nums[i]为最大质数分数的左右两边最远边界。则(left, i) 和 [i, right) 中为子数组左右端点的子数组都可以由nums[i]贡献，\n",
    "        # 同时由乘法原理总共有 (i - left) * (right - i) 个nums[i]贡献\n",
    "\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        MOD = 10 ** 9 + 7\n",
    "        score = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            score[i] = beta[nums[i]]\n",
    "\n",
    "        stk = []\n",
    "        for i, x in enumerate(score):\n",
    "            while stk and score[stk[-1]] < x:\n",
    "                stk.pop()\n",
    "            l[i] = i - stk[-1] if stk else i + 1\n",
    "            stk.append(i)\n",
    "        \n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = score[i]\n",
    "            while stk and score[stk[-1]] <= x:\n",
    "                stk.pop()\n",
    "            r[i] = stk[-1] - i if stk else n - i\n",
    "            stk.append(i)\n",
    "        \n",
    "        # stk = []\n",
    "        # for i, x in enumerate(score):\n",
    "        #     while stk and score[stk[-1]] < x:\n",
    "        #         r[stk.pop()] = i\n",
    "        #     if stk:\n",
    "        #         l[i] = stk[-1]\n",
    "        #     stk.append(i)\n",
    "\n",
    "        res = 1\n",
    "        q = []\n",
    "        for i, x in enumerate(nums):\n",
    "            heappush(q, (-x, i))\n",
    "        \n",
    "\n",
    "        def qpow(a, b):\n",
    "            p = 1\n",
    "            while b:\n",
    "                if b & 1:\n",
    "                    p = (p * a) % MOD\n",
    "                b >>= 1\n",
    "                a = (a * a) % MOD\n",
    "            return p % MOD\n",
    "\n",
    "        while True:\n",
    "            x, i = heappop(q)\n",
    "            x = -x\n",
    "            m = min(l[i] * r[i], k)\n",
    "            k -= m\n",
    "            res = (res * qpow(x, m)) % MOD\n",
    "            if k == 0:\n",
    "                return res % MOD\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        maxval=max(nums);vis=[0]*(maxval+1);pri=[]\n",
    "        for i in range(2,maxval+1):\n",
    "            if(vis[i]==0):pri.append(i);vis[i]=i\n",
    "            for j in pri:\n",
    "                if(i*j>maxval):break\n",
    "                vis[i*j]=j\n",
    "                if(i%j==0):break\n",
    "        n=len(nums)\n",
    "        numv=[0]*n\n",
    "        for i in range(0,n):\n",
    "            j=nums[i]\n",
    "            while(vis[j]):\n",
    "                while(vis[j]==vis[j//vis[j]]):j//=vis[j]\n",
    "                j//=vis[j];numv[i]+=1\n",
    "            if(j!=1):numv[i]+=1\n",
    "        lef,rig,stk=[0]*n,[0]*n,[(1000000,-1)]\n",
    "        for i in range(0,n):\n",
    "            while(stk[-1][0]<numv[i]):del stk[-1]\n",
    "            lef[i]=i-stk[-1][1]\n",
    "            stk.append((numv[i],i))\n",
    "        stk=[(1000000,n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while(stk[-1][0]<=numv[i]):del stk[-1]\n",
    "            rig[i]=stk[-1][1]-i\n",
    "            stk.append((numv[i],i))\n",
    "        nums=sorted([(-nums[i],i) for i in range(0,n)])\n",
    "        ans,mod=1,1000000007\n",
    "        for i in range(0,n):\n",
    "            u,v=-nums[i][0],min(k,lef[nums[i][1]]*rig[nums[i][1]])\n",
    "            while(v):\n",
    "                if(v&1):ans=ans*u%mod\n",
    "                u=u*u%mod;v>>=1\n",
    "            k-=lef[nums[i][1]]*rig[nums[i][1]]\n",
    "            if(k<=0):break\n",
    "        # print(numv,'\\n',lef,'\\n',rig)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_n = 100005\n",
    "alpha = [0]*max_n\n",
    "for i in range(2,max_n):\n",
    "    if alpha[i] != 0: continue\n",
    "    for j in range(i,max_n,i):\n",
    "        alpha[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        def pow(x,n):\n",
    "            if n == 0: return 1\n",
    "            a = pow(x,n>>1)\n",
    "            a = a*a%mod\n",
    "            if n&1: a = a*x%mod\n",
    "            return a\n",
    "\n",
    "        n,mod,ans = len(nums),1000000007,1\n",
    "        st,left,right = [],[-1]*n,[n]*n\n",
    "        score = list(map(lambda x:alpha[x],nums))\n",
    "        for i,(x,s) in enumerate(zip(nums,score)):\n",
    "            while st and score[st[-1]] < s:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        for x,i,l,r in sorted(zip(nums,range(n),left,right),reverse = True):\n",
    "            v = (r-i)*(i-l)\n",
    "            ans = ans*pow(x,min(k,v))%mod\n",
    "            k -= v\n",
    "            if k <= 0: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        mx = max(nums) + 1\n",
    "        omega = [0] * mx\n",
    "        for i in range(2, mx):\n",
    "            if omega[i] == 0:\n",
    "                for j in range(i, mx, i):\n",
    "                    omega[j] += 1\n",
    "        cnt = []\n",
    "        for x in nums:\n",
    "            cnt.append(omega[x])\n",
    "        \n",
    "        s = [-1]\n",
    "        l = [-1] * len(nums)\n",
    "        r = [len(nums)] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            while s[-1] != -1 and cnt[s[-1]] < cnt[i]: \n",
    "                r[s[-1]] = i\n",
    "                s.pop()\n",
    "            l[i] = s[-1]\n",
    "            s.append(i)\n",
    "\n",
    "        e = []\n",
    "        for i in range(len(nums)):\n",
    "            e.append((nums[i], (r[i]-i)*(i-l[i])))\n",
    "        \n",
    "        e = sorted(e, key=lambda x: -x[0])\n",
    "\n",
    "        ans = 1\n",
    "        mod = int(1e9+7)\n",
    "        for x in e:\n",
    "            if x[1] >= k:\n",
    "                ans = ans * pow(x[0], k, mod) % mod\n",
    "                break\n",
    "            else:\n",
    "                ans = ans * pow(x[0], x[1], mod) % mod\n",
    "                k -= x[1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def primes(n):\n",
    "    i = 2\n",
    "    cnt = 0\n",
    "    while i * i <= n:\n",
    "        if n%i == 0:\n",
    "            cnt += 1\n",
    "            while n%i == 0:\n",
    "                n //= i\n",
    "        i += 1\n",
    "    if n > 1:\n",
    "        cnt += 1\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums = [[i, ind, primes(i)] for ind,i in enumerate(nums)]\n",
    "\n",
    "    \n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[st[-1]][2] <= nums[i][2]:\n",
    "                l[st.pop()] = i\n",
    "            st.append(i)\n",
    "        \n",
    "        st = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]][2] < nums[i][2]:\n",
    "                r[st.pop()] = i\n",
    "            st.append(i)\n",
    "        \n",
    "        nums.sort(reverse = True)\n",
    "\n",
    "        cur = 0\n",
    "        p = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        # print(m)\n",
    "        for num, ind, _ in nums:\n",
    "            lb, rb = l[ind], r[ind]\n",
    "            cnt = (ind - lb) * (rb - ind)\n",
    "            req = k - cur\n",
    "            if cnt < req:\n",
    "                p *= pow(num, cnt, mod)\n",
    "                cur += cnt\n",
    "            else:\n",
    "                p *= pow(num, req, mod)\n",
    "                break\n",
    "        \n",
    "        return p % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "f = []\n",
    "vis = [False] * (N + 1)\n",
    "for i in range(2, N + 1):\n",
    "    if not vis[i]:\n",
    "        f.append(i)\n",
    "    for j in f:\n",
    "        if i * j > N:\n",
    "            break\n",
    "        vis[i * j] = True\n",
    "        if i % j == 0:\n",
    "            break\n",
    "mod = 10**9+7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        a = [0] * n\n",
    "        for i, v in enumerate(nums):\n",
    "            j = 0\n",
    "            while j * j <= v:\n",
    "                if v % f[j] == 0:\n",
    "                    a[i] += 1\n",
    "                    while v % f[j] == 0:\n",
    "                        v //= f[j]\n",
    "                j += 1\n",
    "            if v > 1:\n",
    "                a[i] += 1\n",
    "        q = collections.deque()\n",
    "        pre = [0] * n\n",
    "        nxt = [0] * n\n",
    "        h = []\n",
    "        for i, v in enumerate(a):\n",
    "            while q and a[q[-1]] < a[i]:\n",
    "                nxt[q[-1]] = i\n",
    "                q.pop()\n",
    "            if q:\n",
    "                pre[i] = q[-1]\n",
    "            q.append(i)\n",
    "            heapq.heappush(h, [-nums[i], i])\n",
    "        while q and a[q[-1]] < inf:\n",
    "            nxt[q[-1]] = n - 1\n",
    "            q.pop()\n",
    "        ans = 1\n",
    "        while h:\n",
    "            _, i = heapq.heappop(h)\n",
    "            left = pre[i] + 1 if a[pre[i]] >= a[i] else pre[i]\n",
    "            right = nxt[i] - 1 if a[i] < a[nxt[i]] else nxt[i]\n",
    "            d1 = i - left + 1 if i >= left else 1\n",
    "            d2 = right - i + 1 if right >= i else 1\n",
    "            d = d1 * d2\n",
    "            if k >= d:\n",
    "                k -= d\n",
    "                ans *= pow(nums[i], d, mod)\n",
    "                ans %= mod\n",
    "            else:\n",
    "                ans *= pow(nums[i], k, mod)\n",
    "                ans %= mod\n",
    "                k = 0\n",
    "            if not k:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primeCount = [0]*100001\n",
    "for i in range(2, 100001):\n",
    "    if not primeCount[i]:\n",
    "        for j in range(i, 100001, i):\n",
    "            primeCount[j] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # print(self.primeCount[:20])\n",
    "\n",
    "        leftBound = []\n",
    "        rightBound = [len(nums)-1] * len(nums)\n",
    "        stack = []\n",
    "        for index in range(len(nums)):\n",
    "            while len(stack) and primeCount[nums[stack[-1]]] < primeCount[nums[index]]:\n",
    "                t = stack.pop()\n",
    "                rightBound[t] = index-1\n",
    "            leftBound.append(0 if not stack else stack[-1]+1)\n",
    "            stack.append(index)\n",
    "\n",
    "        array = sorted([(nums[i], i) for i in range(len(nums))], reverse=True)\n",
    "        ans = 1\n",
    "        for num, index in array:\n",
    "            cnt = min(k, (index-leftBound[index]+1)*(rightBound[index]-index+1))\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            ans = ans*pow(num, cnt, 1000000007) % 1000000007\n",
    "            k -= cnt\n",
    "            if not k: break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "primeCount = [0]*100001\n",
    "for i in range(2, 100001):\n",
    "    if not primeCount[i]:\n",
    "        for j in range(i, 100001, i):\n",
    "            primeCount[j] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # print(self.primeCount[:20])\n",
    "\n",
    "        leftBound = []\n",
    "        stack = []\n",
    "        for index in range(len(nums)):\n",
    "            while len(stack) and primeCount[nums[stack[-1]]] < primeCount[nums[index]]:\n",
    "                stack.pop()\n",
    "            leftBound.append(0 if not stack else stack[-1]+1)\n",
    "            stack.append(index)\n",
    "\n",
    "        rightBound = []\n",
    "        stack = []\n",
    "        for index in range(len(nums)-1, -1, -1):\n",
    "            while len(stack) and primeCount[nums[stack[-1]]] <= primeCount[nums[index]]:\n",
    "                stack.pop()\n",
    "            rightBound.append(len(nums)-1 if not stack else stack[-1]-1)\n",
    "            stack.append(index)\n",
    "        rightBound = rightBound[::-1]\n",
    "\n",
    "        def mypow(num, cnt):\n",
    "            base = num\n",
    "            ret = 1\n",
    "            while cnt:\n",
    "                if cnt&1:\n",
    "                    ret = ret * base % 1000000007\n",
    "                base = base * base % 1000000007\n",
    "                cnt >>= 1\n",
    "            return ret\n",
    "\n",
    "        array = sorted([(nums[i], i) for i in range(len(nums))], reverse=True)\n",
    "        ans = 1\n",
    "        for num, index in array:\n",
    "            cnt = min(k, (index-leftBound[index]+1)*(rightBound[index]-index+1))\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            ans = ans*mypow(num, cnt) % 1000000007\n",
    "            k -= cnt\n",
    "            if not k: break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        isPrime = [1]*1000\n",
    "        for i in range(2,1000):\n",
    "            if isPrime[i]:\n",
    "                for j in range(i*2, 1000, i):\n",
    "                    isPrime[j] = 0\n",
    "\n",
    "        prime = []\n",
    "        for i in range(2, 1000): \n",
    "            if isPrime[i]:\n",
    "                prime.append(i)\n",
    "\n",
    "        def getPrimeCount(num):\n",
    "            i = 0\n",
    "            ret = 0\n",
    "            while prime[i]**2 <= num and num != 1:\n",
    "                if num % prime[i] == 0:\n",
    "                    while num % prime[i] == 0:\n",
    "                        num //= prime[i]\n",
    "                    ret += 1\n",
    "                i += 1\n",
    "            return ret + (num != 1)\n",
    "\n",
    "        primeCount = [getPrimeCount(i) for i in nums]\n",
    "\n",
    "        # print(primeCount)\n",
    "\n",
    "        leftBound = []\n",
    "        stack = []\n",
    "        for index in range(len(nums)):\n",
    "            while len(stack) and primeCount[stack[-1]] < primeCount[index]:\n",
    "                stack.pop()\n",
    "            leftBound.append(0 if not stack else stack[-1]+1)\n",
    "            stack.append(index)\n",
    "\n",
    "        rightBound = []\n",
    "        stack = []\n",
    "        for index in range(len(nums)-1, -1, -1):\n",
    "            while len(stack) and primeCount[stack[-1]] <= primeCount[index]:\n",
    "                stack.pop()\n",
    "            rightBound.append(len(nums)-1 if not stack else stack[-1]-1)\n",
    "            stack.append(index)\n",
    "        rightBound = rightBound[::-1]\n",
    "\n",
    "        def mypow(num, cnt):\n",
    "            base = num\n",
    "            ret = 1\n",
    "            while cnt:\n",
    "                if cnt&1:\n",
    "                    ret = ret * base % 1000000007\n",
    "                base = base * base % 1000000007\n",
    "                cnt >>= 1\n",
    "            return ret\n",
    "\n",
    "        array = sorted([(nums[i], i) for i in range(len(nums))], reverse=True)\n",
    "        ans = 1\n",
    "        for num, index in array:\n",
    "            cnt = min(k, (index-leftBound[index]+1)*(rightBound[index]-index+1))\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            ans = ans*mypow(num, cnt) % 1000000007\n",
    "            k -= cnt\n",
    "            if not k: break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "MX = 10 ** 5 + 1\n",
    "omega = [0] * MX\n",
    "for i in range(2, MX):\n",
    "    if omega[i] == 0:\n",
    "        for j in range(i, MX, i):\n",
    "            omega[j] += 1\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n \n",
    "        right = [n] * n \n",
    "        st = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while st and omega[nums[st[-1]]] < omega[v]:\n",
    "                right[st.pop()] = i \n",
    "            if st:left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ans = 1\n",
    "        for i, v, l, r in sorted(zip(range(n), nums, left, right), key = lambda z: -z[1]):\n",
    "            tot = (i - l) * (r - i)\n",
    "            if tot >= k:\n",
    "                ans = ans * pow(v, k, mod) % mod \n",
    "                break \n",
    "            ans = ans * pow(v, tot, mod) % mod \n",
    "            k -= tot \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD, MX = 10 ** 9 + 7, 10 ** 5 + 1\n",
    "omega = [0] * MX\n",
    "for i in range(2, MX):\n",
    "    if omega[i] == 0:\n",
    "        for j in range(i, MX, i):\n",
    "            omega[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and omega[nums[st[-1]]] < omega[x]:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ans = 1\n",
    "        for i, x, l, r in sorted(zip(range(n), nums, left, right), key = lambda z : -z[1]):\n",
    "            tot = (i - l) * (r - i)\n",
    "            if tot >= k:\n",
    "                ans = ans * pow(x, k, MOD) % MOD\n",
    "                break\n",
    "            ans = ans * pow(x, tot, MOD) % MOD\n",
    "            k -= tot\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "MX = 10 ** 5 + 1\n",
    "omega = [0] * MX\n",
    "for i in range(2, MX):  # 预处理 omega\n",
    "    if omega[i] == 0:  # i 是质数\n",
    "        for j in range(i, MX, i):\n",
    "            omega[j] += 1  # i 是 j 的一个质因子\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n  # 质数分数 >= omega[nums[i]] 的左侧最近元素下标\n",
    "        right = [n] * n  # 质数分数 >  omega[nums[i]] 的右侧最近元素下标\n",
    "        st = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while st and omega[nums[st[-1]]] < omega[v]:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 1\n",
    "        for i, v, l, r in sorted(zip(range(n), nums, left, right), key=lambda z: -z[1]):\n",
    "            tot = (i - l) * (r - i)\n",
    "            if tot >= k:\n",
    "                ans = ans * pow(v, k, MOD) % MOD\n",
    "                break\n",
    "            ans = ans * pow(v, tot, MOD) % MOD\n",
    "            k -= tot  # 更新剩余操作次数\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        isPrime = [1]*1000\n",
    "        for i in range(2,1000):\n",
    "            if isPrime[i]:\n",
    "                for j in range(i*2, 1000, i):\n",
    "                    isPrime[j] = 0\n",
    "\n",
    "        prime = []\n",
    "        for i in range(2, 1000): \n",
    "            if isPrime[i]:\n",
    "                prime.append(i)\n",
    "        @cache\n",
    "        def getPrimeCount(num):\n",
    "            i = 0\n",
    "            ret = 0\n",
    "            while prime[i]**2 <= num and num != 1:\n",
    "                if num % prime[i] == 0:\n",
    "                    while num % prime[i] == 0:\n",
    "                        num //= prime[i]\n",
    "                    ret += 1\n",
    "                i += 1\n",
    "            return ret + (num != 1)\n",
    "\n",
    "        primeCount = [getPrimeCount(i) for i in nums]\n",
    "\n",
    "        # print(primeCount)\n",
    "\n",
    "        leftBound = []\n",
    "        stack = []\n",
    "        for index in range(len(nums)):\n",
    "            while len(stack) and primeCount[stack[-1]] < primeCount[index]:\n",
    "                stack.pop()\n",
    "            leftBound.append(0 if not stack else stack[-1]+1)\n",
    "            stack.append(index)\n",
    "\n",
    "        rightBound = []\n",
    "        stack = []\n",
    "        for index in range(len(nums)-1, -1, -1):\n",
    "            while len(stack) and primeCount[stack[-1]] <= primeCount[index]:\n",
    "                stack.pop()\n",
    "            rightBound.append(len(nums)-1 if not stack else stack[-1]-1)\n",
    "            stack.append(index)\n",
    "        rightBound = rightBound[::-1]\n",
    "\n",
    "        def mypow(num, cnt):\n",
    "            base = num\n",
    "            ret = 1\n",
    "            while cnt:\n",
    "                if cnt&1:\n",
    "                    ret = ret * base % 1000000007\n",
    "                base = base * base % 1000000007\n",
    "                cnt >>= 1\n",
    "            return ret\n",
    "\n",
    "        array = sorted([(nums[i], i) for i in range(len(nums))], reverse=True)\n",
    "        ans = 1\n",
    "        for num, index in array:\n",
    "            cnt = min(k, (index-leftBound[index]+1)*(rightBound[index]-index+1))\n",
    "            # print(num, index, leftBound[index], rightBound[index])\n",
    "            ans = ans*mypow(num, cnt) % 1000000007\n",
    "            k -= cnt\n",
    "            if not k: break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "MOD = 10 ** 9 + 7\n",
    "f = [0] * MX\n",
    "for i in range(2, MX):\n",
    "    if not f[i]:\n",
    "        for j in range(i, MX, i):\n",
    "            f[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, a: List[int], k: int) -> int:\n",
    "        n = len(a)\n",
    "        # 左边的质数分数【大于或等于】的最近数的下标\n",
    "        # 右边的质数分数【大于】的最近数的下标\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        st = [] # 存下标\n",
    "        for i, v in enumerate(a):\n",
    "            while st and f[a[st[-1]]] < f[v]:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        res = 1\n",
    "        for i, v, L, R in sorted(zip(range(n), a, left, right), key=lambda z : -z[1]):\n",
    "            total = (i - L) * (R - i)\n",
    "            if total >= k:\n",
    "                res = res * pow(v, k, MOD) % MOD\n",
    "                break\n",
    "            res = res * pow(v, total, MOD) % MOD\n",
    "            k -= total\n",
    "        return res\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "MX = 10 ** 5 + 1\n",
    "omega = [0] * MX\n",
    "for i in range(2, MX):\n",
    "    if omega[i] == 0:\n",
    "        for j in range(i, MX, i):\n",
    "            omega[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = [-1]\n",
    "        for i, x in enumerate(nums):\n",
    "            while len(st) > 1 and omega[nums[st[-1]]] < omega[x]:\n",
    "                right[st.pop()] = i\n",
    "            left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ans = 1\n",
    "        for i, x, l, r in sorted(zip(range(n), nums, left, right), key=lambda z: -z[1]):\n",
    "            print(i, x)\n",
    "            tot = (i - l) * (r - i)\n",
    "            if tot >= k:\n",
    "                ans = ans * pow(x, k, MOD) % MOD\n",
    "                break\n",
    "            ans = ans * pow(x, tot, MOD) % MOD\n",
    "            k -= tot\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "omega = [0] * MX\n",
    "for i in range(2, MX):  # 预处理 omega\n",
    "    if omega[i] == 0:  # i 是质数\n",
    "        for j in range(i, MX, i):\n",
    "            omega[j] += 1  # i 是 j 的一个质因子\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def getprime(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            results = []\n",
    "            i = 2\n",
    "            while i <= x:\n",
    "                if i == x:\n",
    "                    results.append(x)\n",
    "                    break\n",
    "                elif x % i == 0:\n",
    "                    results.append(i)\n",
    "                    while x % i == 0:\n",
    "                        x = x // i\n",
    "                else:\n",
    "                    i = i + 1\n",
    "            return len(results)\n",
    "        \n",
    "        # score = [ getprime(i) for i in nums]\n",
    "        score = [ omega[i] for i in nums] \n",
    "        # print(score)\n",
    "        hq = [(-item, i) for i, item in enumerate(nums)]\n",
    "        heapify(hq)\n",
    "        # heappush.push(hq, ())\n",
    "        # print(hq)\n",
    "\n",
    "        # 单调栈\n",
    "        left = [0] * n\n",
    "        right = [n - 1] * n\n",
    "        st = []\n",
    "        # print(score)\n",
    "        for i, item in enumerate(nums):\n",
    "            while st and score[st[-1]] < score[i]:\n",
    "                right[st.pop()] = i - 1\n",
    "            if st:\n",
    "                left[i] = st[-1] + 1\n",
    "            st.append(i)\n",
    "        # print(left)\n",
    "        # st = []\n",
    "        # right = [n - 1] * n\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     # print(right)\n",
    "        #     while st and score[st[-1]] <= score[i]:\n",
    "        #         st.pop()\n",
    "        #     if st:\n",
    "        #         right[i] = st[-1] - 1\n",
    "        #     st.append(i)\n",
    "        # print(right)\n",
    "\n",
    "        ans = 1\n",
    "        while hq:\n",
    "            if k <= 0:\n",
    "                break\n",
    "            item, index = heappop(hq)\n",
    "            \n",
    "            # r = index\n",
    "            # for t in range(index + 1, n + 1):\n",
    "            #     if t == n or score[t] > score[index]:\n",
    "            #         r = t - 1\n",
    "            #         break\n",
    "            # l = index\n",
    "            # for t in range(index - 1, -2, -1):\n",
    "            #     if t == -1 or score[t] >= score[index]:\n",
    "            #         l = t + 1\n",
    "            #         break\n",
    "            #     # if score[index] > score[t]:\n",
    "            #     #     pass\n",
    "            #     # else:\n",
    "            #     #     l = t + 1\n",
    "            #     #     break\n",
    "            # 只要含i的范围 都可以使用-item\n",
    "            # now_num = min((index - l + 1) * (r - index + 1), k)\n",
    "            now_num = min((index - left[index] + 1) * (right[index] - index + 1), k)\n",
    "            # print(l, index, r ,now_num, item)\n",
    "            # print(left[index], index, right[index] ,now_num, item)\n",
    "            ans = ans * pow(-item, now_num, MOD) % MOD\n",
    "            # for i in range(now_num):\n",
    "                \n",
    "            #     ans = (ans * (-item)) % MOD\n",
    "            k = k - now_num\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "maxi = 10 ** 5\n",
    "score = [0] * (maxi + 1)\n",
    "for i in range(2, maxi + 1):\n",
    "    if not score[i]:\n",
    "        for j in range(i, maxi + 1, i):\n",
    "            score[j] += 1\n",
    "\n",
    "@cache\n",
    "def get_factor_num(x):\n",
    "    return score[x]\n",
    "\n",
    "right = [0] * (10**5 + 1)\n",
    "left = [0] * (10**5 + 1)\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k0: int) -> int:\n",
    "        n = len(nums)\n",
    "        st1 = []  # 单调递减\n",
    "        st2 = []  # 单调递减\n",
    "        \n",
    "        for i, x1 in enumerate(nums):\n",
    "            while st1 and st1[-1][1] < get_factor_num(x1):\n",
    "                st1.pop()\n",
    "            x2 = nums[n - i - 1]\n",
    "            while st2 and st2[-1][1] <= get_factor_num(x2):\n",
    "                st2.pop()\n",
    "            if st1:\n",
    "                left[i] = st1[-1][0]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            if st2:\n",
    "                right[n - i - 1] = st2[-1][0]\n",
    "            else:\n",
    "                right[n - i - 1] = n\n",
    "            st1.append((i, get_factor_num(x1)))\n",
    "            st2.append((n - i - 1, get_factor_num(x2)))\n",
    "\n",
    "        c = Counter()\n",
    "        for i, x in enumerate(nums):\n",
    "            j = left[i]\n",
    "            k = right[i]\n",
    "            delta = (k - i) * (i - j)\n",
    "            c[x] += delta\n",
    "        s = sorted(c.items())\n",
    "        ans = 1\n",
    "        while k0:\n",
    "            x, delta = s.pop()\n",
    "            delta = min(delta, k0)\n",
    "            ans = (ans * pow(x, delta, MOD)) % MOD\n",
    "            k0 -= delta\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "prime_score = [0] * (10 ** 5 + 1)\n",
    "for v in range(2, 10 ** 5 + 1):\n",
    "    if prime_score[v] > 0:\n",
    "        continue\n",
    "    prime_score[v] = 1\n",
    "    cur = v * 2 \n",
    "    while cur < len(prime_score):\n",
    "        prime_score[cur] += 1\n",
    "        cur += v \n",
    "                \n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "                \n",
    "        n = len(nums)\n",
    "        left_max = [-1] * n \n",
    "        mono = []\n",
    "        for i, v in enumerate(nums):\n",
    "            score = prime_score[v]\n",
    "            while mono and prime_score[nums[mono[-1]]] < score:\n",
    "                mono.pop()\n",
    "            if mono:\n",
    "                left_max[i] = mono[-1]\n",
    "            mono.append(i)\n",
    "            \n",
    "        score_cnt = []\n",
    "        mono = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            score = prime_score[nums[i]]\n",
    "            while mono and prime_score[nums[mono[-1]]] <= score:\n",
    "                mono.pop()\n",
    "            right_max = mono[-1] if mono else n \n",
    "            score_cnt.append((nums[i], (i - left_max[i]) * (right_max - i)))\n",
    "            mono.append(i)\n",
    "        \n",
    "        ans = 1\n",
    "        for score, cnt in sorted(score_cnt, key=lambda x: (-x[0], -x[1])):\n",
    "            if score == 1:\n",
    "                break\n",
    "            if cnt >= k:\n",
    "                ans = (ans * pow(score, k, MOD)) % MOD\n",
    "                break\n",
    "            ans = (ans * pow(score, cnt, MOD)) % MOD\n",
    "            k -= cnt \n",
    "        return ans \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from math import sqrt\n",
    "MOD = 10 ** 9 + 7\n",
    "primes = [2]\n",
    "n = 10 ** 5\n",
    "is_prime = [True] * (n + 1)\n",
    "is_prime[0] = is_prime[1] = False\n",
    "for i in range(2, int(sqrt(n)) + 1):\n",
    "    if is_prime[i]:\n",
    "        j = i * i\n",
    "        while j <= n:\n",
    "            is_prime[j] = False\n",
    "            j += i\n",
    "for i in range(3, n + 1, 2):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "\n",
    "@lru_cache(None)\n",
    "def f(num: int) -> int:\n",
    "            x = set()\n",
    "            while num > 1:\n",
    "                for p in primes:\n",
    "                    if p > num:\n",
    "                        break\n",
    "                    while num % p == 0:\n",
    "                        x.add(p)\n",
    "                        num //= p\n",
    "            return len(x)\n",
    "\n",
    "inf = 2 ** 31 - 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        x = [0] * n\n",
    "        left = [-1] * n\n",
    "        stk = [(inf, -1)]\n",
    "        for idx, u in enumerate(nums):\n",
    "            x[idx] = f(u)\n",
    "            num = x[idx]\n",
    "            while stk[-1][0] < num:\n",
    "                stk.pop()\n",
    "            left[idx] = stk[-1][1]\n",
    "            stk.append((num, idx))\n",
    "        right = [n] * n\n",
    "        stk = [(inf, n)]\n",
    "        for idx in range(n - 1, -1, -1):\n",
    "            num = x[idx]\n",
    "            while stk[-1][0] <= num:\n",
    "                stk.pop()\n",
    "            right[idx] = stk[-1][1]\n",
    "            stk.append((num, idx))\n",
    "        cnts = [(right[i] - i) * (i - left[i]) for i in range(n)]\n",
    "        ret = 1\n",
    "        for num, cnt in sorted(zip(nums, cnts), reverse=True):\n",
    "            if cnt < k:\n",
    "                ret *= pow(num, cnt, MOD)\n",
    "                ret %= MOD\n",
    "                k -= cnt\n",
    "            else:\n",
    "                ret *= pow(num, k, MOD)\n",
    "                ret %= MOD\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5+1\n",
    "score = [0] * MX\n",
    "for i in range(2, MX):\n",
    "    if score[i] == 0:\n",
    "        for j in range(i,MX,i):\n",
    "            score[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        numsPos = [[nums[i], i] for i in range(n)]\n",
    "        numsPos.sort(reverse=True)\n",
    "        MOD = 10**9+7\n",
    "        \n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        s = [[inf,-1]]\n",
    "        for i in range(n):\n",
    "            while s[-1][0] < score[nums[i]]:\n",
    "                s.pop()\n",
    "            left[i] = i - s[-1][1]\n",
    "            s.append([score[nums[i]],i])\n",
    "        s = [[inf,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while s[-1][0] <= score[nums[i]]:\n",
    "                s.pop()\n",
    "            right[i] = s[-1][1] - i\n",
    "            s.append([score[nums[i]],i])\n",
    "\n",
    "        idx = 0\n",
    "        res = 1\n",
    "\n",
    "        while k > 0:\n",
    "            cur = numsPos[idx][0]\n",
    "            pos = numsPos[idx][1]\n",
    "            l = left[pos]\n",
    "            r = right[pos]\n",
    "            c = min(k, l*r)\n",
    "            k -= c\n",
    "            POW = cur\n",
    "            temp = 1\n",
    "            res = res * pow(cur,c,MOD) % MOD      \n",
    "            idx += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "MX = 10 ** 5 + 1\n",
    "cnt=[0]*MX\n",
    "for i in range(2,MX):\n",
    "    if cnt[i]==0:\n",
    "        for j in range(i,MX,i):\n",
    "            cnt[j] +=1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n=len(nums)\n",
    "       \n",
    "        amnt=[0]*n\n",
    "        for i,v in enumerate(nums):\n",
    "            amnt[i]=cnt[v] \n",
    "        #print(amnt)\n",
    "        l=[-1]*n\n",
    "        r=[n]*n\n",
    "        stack=[]\n",
    "        for i in range(n):\n",
    "            while stack and amnt[i]>stack[-1][1]:\n",
    "                r[stack[-1][0]]=i\n",
    "                stack.pop()\n",
    "            if len(stack)==0:\n",
    "                l[i]=-1\n",
    "            elif amnt[i]<=stack[-1][1]:\n",
    "                l[i]=stack[-1][0]\n",
    "            stack.append([i,amnt[i]])\n",
    "\n",
    "        #print(l)\n",
    "        #print(r)\n",
    "        tot=[0]*n\n",
    "        for i in range(n):\n",
    "            tot[i]=(i-l[i])*(r[i]-i)\n",
    "        \n",
    "        #print(tot)\n",
    "        arr=sorted(zip(nums,tot),reverse=True)\n",
    "        \n",
    "        def multi(x,y,n):\n",
    "            ans = 0\n",
    "            ans=x%n\n",
    "            ans=ans*(y%n)%n\n",
    "            return ans\n",
    "\n",
    "        def multimod(x,y,mod):\n",
    "            ans=1\n",
    "            while(y!=0):  \n",
    "                if y%2:         #奇数\n",
    "                    ans=multi(ans,x,mod)\n",
    "                x=multi(x,x,mod)\n",
    "                y=y//2          #整除2\n",
    "            return ans\n",
    "\n",
    "        \n",
    "        res=1\n",
    "        for a,b in arr:\n",
    "            if b>=k:\n",
    "                res =multi(res,multimod(a,k,MOD),MOD)\n",
    "                break\n",
    "            else:\n",
    "                res =multi(res,multimod(a,b,MOD),MOD)\n",
    "                k -=b\n",
    "        \n",
    "        return res  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def getScore(num):\n",
    "            res = 0\n",
    "\n",
    "            d = 2\n",
    "            while d * d <= num:  # 分解质因数\n",
    "                if num % d == 0:\n",
    "                    res += 1\n",
    "                    \n",
    "                while num % d == 0:\n",
    "                    num //= d\n",
    "                d += 1\n",
    "            if num > 1:\n",
    "                res += 1\n",
    "\n",
    "            return res\n",
    "        \n",
    "        n = len(nums)\n",
    "        # 单调栈，每个值的 质数分数 管理范围\n",
    "        left = [0] * n\n",
    "        right = [n-1] * n\n",
    "        # 单调栈，递减\n",
    "        # 分数，i\n",
    "        que = deque()\n",
    "        \n",
    "        # tmp = []\n",
    "        \n",
    "        # 贪心，数字最大堆\n",
    "        heap = []\n",
    "        \n",
    "        # 获取 管理区域\n",
    "        for i,num in enumerate(nums):\n",
    "            score = getScore(num)\n",
    "            # tmp.append(score)\n",
    "            heappush(heap,(-num,i))\n",
    "            \n",
    "            \n",
    "            while que and que[-1][0] < score:\n",
    "                right[que.pop()[1]] = i - 1\n",
    "            \n",
    "            if que:\n",
    "                left[i] = que[-1][1] + 1\n",
    "            \n",
    "            que.append((score,i))\n",
    "        \n",
    "        # print(tmp)\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        \n",
    "        res = 1\n",
    "        MAX_NUM = int(1e9+7)\n",
    "        while k:\n",
    "            # 弹出最大堆堆顶\n",
    "            num,pos = heappop(heap)\n",
    "            num = -num\n",
    "            # 根据堆顶数字对应的位置 pos 获取管理范围\n",
    "            # 根据乘法原理，知道可以取多少个子数组\n",
    "            d = (pos - left[pos] + 1) * (right[pos] - pos + 1)\n",
    "            \n",
    "            # 减去操作次数，更新结果得分res\n",
    "            if k >= d:\n",
    "                k -= d\n",
    "                # 快速幂\n",
    "                res *= pow(num,d,MAX_NUM)\n",
    "                res %= MAX_NUM\n",
    "            else:\n",
    "                res *= pow(num,k,MAX_NUM)\n",
    "                res %= MAX_NUM\n",
    "                k = 0\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "vx=10**5+5\n",
    "prime=[[] for i in range(vx)]\n",
    "for i in range(2,vx):\n",
    "    if not prime[i]:\n",
    "        prime[i].append(i)\n",
    "        for j in range(i+i,vx,i):\n",
    "            prime[j].append(i)\n",
    "class Solution:\n",
    "    def maximumScore(self, a: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(a)\n",
    "        b=[len(prime[i]) for i in a]\n",
    "        l=[-1]*n\n",
    "        r=[n]*n\n",
    "        st=[]\n",
    "        for i in range(n):\n",
    "            while st and b[st[-1]]<b[i]:\n",
    "                r[st[-1]]=i\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        st=[]\n",
    "        for i in reversed(range(n)):\n",
    "            while st and b[st[-1]]<=b[i]:\n",
    "                l[st[-1]]=i\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        ans=1\n",
    "        c=sorted(range(n),key=lambda x:-a[x])\n",
    "        for i in c:\n",
    "            d=(i-l[i])*(r[i]-i)\n",
    "            e=min(k,d)\n",
    "            k-=e\n",
    "            ans=ans*pow(a[i],e,mod)%mod\n",
    "            # print(i,l[i],r[i],d,e,k,ans)\n",
    "            if k<=0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "Y = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n",
    "class Solution:\n",
    "    MODS = 10 ** 9 + 7\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def get_num(x):\n",
    "            res = 0\n",
    "            for ii in Y:\n",
    "                flag = True\n",
    "                while x % ii == 0:\n",
    "                    if flag:\n",
    "                        res += 1\n",
    "                    x //= ii\n",
    "                    flag = False\n",
    "            if x != 1:\n",
    "                res += 1\n",
    "            return res\n",
    "        N = len(nums)\n",
    "        y = [get_num(ii) for ii in nums]\n",
    "        r = [N] * N\n",
    "        l = [-1] * N\n",
    "        q = []\n",
    "        for ii in range(N):\n",
    "            now = y[ii]\n",
    "            while q and q[-1][0] < now:\n",
    "                pre = q.pop()\n",
    "                r[pre[1]] = ii\n",
    "            q.append((now, ii))\n",
    "        q = []\n",
    "        for ii in range(N):\n",
    "            now = y[ii]\n",
    "            while q and q[-1][0] < now:\n",
    "                pre = q.pop()\n",
    "                r[pre[1]] = ii\n",
    "            if q:\n",
    "                l[ii] = q[-1][1]\n",
    "            q.append((now, ii))\n",
    "        # print(y, l, r)\n",
    "        res = 1\n",
    "        for idx, now in sorted(enumerate(nums), key=lambda i:(-i[1])):\n",
    "            r_idx = r[idx]\n",
    "            l_idx = l[idx]\n",
    "            t = r_idx - idx + (idx - l_idx - 1) * (r_idx - idx)\n",
    "            # print(k, t, idx, now)\n",
    "            if t >= k:\n",
    "                res = (res * pow(now, k, self.MODS)) % self.MODS\n",
    "                break\n",
    "            res = (res * pow(now, t, self.MODS)) % self.MODS\n",
    "            k -= t\n",
    "        return res\n",
    "            \n",
    "            \n",
    "        \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dp = [0] * (10 ** 5 + 1)\n",
    "for i in range(2, 10 ** 5 + 1):\n",
    "    if dp[i] == 0:\n",
    "        for j in range(i, (10 ** 5 + 1), i):\n",
    "            dp[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        d = [dp[i] for i in nums]\n",
    "        # print(d)\n",
    "        p = []\n",
    "        v = [None]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            s = i\n",
    "            while p and d[p[-1]] < d[i]:\n",
    "                s = p.pop()\n",
    "            # print(p)\n",
    "            if not p:\n",
    "                s = 0\n",
    "            else:\n",
    "                s = p[-1]+1\n",
    "            p.append(i)\n",
    "            # print(p, i)\n",
    "            if s != i:\n",
    "                v[i] = [s, i-1, nums[i], i]\n",
    "        # print(v)\n",
    "        nums2 = nums[::-1]\n",
    "        d = [dp[i] for i in nums2]\n",
    "        p = []\n",
    "        for i in range(len(nums2)):\n",
    "            s = i\n",
    "            while p and d[p[-1]] <= d[i]:\n",
    "                s = p.pop()\n",
    "            if not p:\n",
    "                s = 0\n",
    "            else:\n",
    "                s = p[-1]+1\n",
    "            p.append(i)\n",
    "            if v[len(nums2)-i-1]:\n",
    "                v[len(nums2)-i-1][1] = len(nums2)-s-1\n",
    "            else:\n",
    "                v[len(nums2)-i-1] = [len(nums2)-i-1, len(nums2)-s-1, nums2[i], len(nums2)-i-1]\n",
    "        # print(v)\n",
    "        res = 1\n",
    "        for i, j, val, inx in sorted(v, key=lambda x: x[2])[::-1]:\n",
    "            p = (inx-i+1)*(j-inx+1)\n",
    "            # print(i, j, inx, p, val)\n",
    "            c = min(p, k)\n",
    "            res *= pow(val, c, 10**9+7)\n",
    "            res %= 10**9+7\n",
    "            k -= c\n",
    "            if k == 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "isprime = [True]*10**3\n",
    "isprime[0] = isprime[1] = False\n",
    "primes = []\n",
    "for i in range(len(isprime)):\n",
    "    if not isprime[i]:continue\n",
    "    primes.append(i)\n",
    "    for j in range(i*2, len(isprime), i):\n",
    "        isprime[j] = False\n",
    "MOD = 10**9+7\n",
    "def primecnt(i):\n",
    "    cnt = 0\n",
    "    for j in primes:\n",
    "        if i<j**2:break\n",
    "        if i%j==0:\n",
    "            cnt+=1\n",
    "            while(i%j==0):\n",
    "                i//=j\n",
    "    if i!=1:\n",
    "        cnt+=1\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        score = [primecnt(i)for i in nums]\n",
    "        LR = {}\n",
    "        width = [0]*len(score)\n",
    "        for i,n in sorted(enumerate(score), key = lambda x:(x[1],-x[0])):\n",
    "            L = LR.get(i,i)\n",
    "            R = LR.get(i+1,i+1)\n",
    "            LR[L] = R\n",
    "            LR[R] = L\n",
    "            width[i] = ((i-L+1)*(R-i))\n",
    "        out = 1\n",
    "        for n,w in sorted(zip(nums,width),reverse = True):\n",
    "            if k>w:\n",
    "                k-=w\n",
    "                out = (out*pow(n,w,MOD))%MOD\n",
    "            else:\n",
    "                out = (out*pow(n,k,MOD))%MOD\n",
    "                break\n",
    "        return out\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 100000\r\n",
    "isprime = [True] * (n + 1)\r\n",
    "primes = []\r\n",
    "for i in range(2, n + 1):\r\n",
    "    if isprime[i]:\r\n",
    "        primes.append(i)\r\n",
    "    for p in primes:\r\n",
    "        if p * i > n:\r\n",
    "            break \r\n",
    "        isprime[i * p] = False \r\n",
    "        if i % p == 0:\r\n",
    "            break \r\n",
    "@cache\r\n",
    "def defactor(num):\r\n",
    "    cnt = 0\r\n",
    "    for p in primes:\r\n",
    "        if num % p == 0:\r\n",
    "            cnt += 1\r\n",
    "            while num % p == 0:\r\n",
    "                num //= p \r\n",
    "        if p > num:\r\n",
    "            break \r\n",
    "    if num > 1:\r\n",
    "        cnt += 1\r\n",
    "    return cnt \r\n",
    " \r\n",
    "class Solution:\r\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\r\n",
    "        aux = [defactor(num) for num in nums]\r\n",
    "        n = len(nums)\r\n",
    "        f = [-1] * n \r\n",
    "        b = [n] * n\r\n",
    "        stack = []\r\n",
    "        for i in range(n):\r\n",
    "            while stack and aux[stack[-1]] < aux[i]:\r\n",
    "                idx = stack.pop()\r\n",
    "                b[idx] = i\r\n",
    "            if stack:\r\n",
    "                f[i] = stack[-1]\r\n",
    "            stack.append(i)\r\n",
    "\r\n",
    "        queue = []\r\n",
    "        tmp = [[num, i] for i, num in enumerate(nums)]\r\n",
    "        tmp.sort(reverse = True)\r\n",
    "\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        res = 1\r\n",
    "        idx = 0\r\n",
    "        while k:\r\n",
    "            num, i = tmp[idx]\r\n",
    "            t = min(k, (i - f[i])*(b[i] - i))\r\n",
    "            res *= pow(num, t, mod)\r\n",
    "            k -= t\r\n",
    "            res %= mod\r\n",
    "            idx += 1\r\n",
    "        return res\r\n",
    "            \r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10**5+10\n",
    "\n",
    "# 对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目\n",
    "# x = d∣x ∑ φ(d)\n",
    "phi = [0] * N\n",
    "phi[1] = 1\n",
    "pfact = [0] * N\n",
    "# fact = [[] for _ in range(N)]\n",
    "primes = []\n",
    "\n",
    "# 1）莫比乌斯函数μ(n)的定义域是N；\n",
    "# 2）μ(1)=1；\n",
    "# 3）当n存在平方因子时，μ(n)=0；\n",
    "# 4）当n是素数或奇数个不同素数之积时，μ(n)=-1；\n",
    "# 5）当n是偶数个不同素数之积时，μ(n)=1。\n",
    "# d∣n ∑ μ(d) = [n == 1]\n",
    "\n",
    "# d∣n ∑ μ(d) * (n / d) = φ(n)\n",
    "\n",
    "# g(n) = d∣n ∑ f(d) <---> f(n) = d∣n ∑ μ(d) g(n/d)\n",
    "# g(n) = d∣n ∑ f(n) <---> f(n) = d∣n ∑ μ(n/d) g(n)\n",
    "# mobious = [0] * N\n",
    "# mobious[1] = 1\n",
    "\n",
    "for i in range(1, N):\n",
    "    if not phi[i]:\n",
    "        primes.append(i)\n",
    "        phi[i] = i-1\n",
    "        # mobious[i] = -1\n",
    "        for j in range(1, N):\n",
    "            if i * j >= N:\n",
    "                break\n",
    "            pfact[i*j] = i\n",
    "    for j in primes:\n",
    "        if i * j >= N:\n",
    "            break\n",
    "        if i % j == 0:\n",
    "            phi[i*j] = phi[i] * j\n",
    "            # mobious[i*j] = 0\n",
    "            break\n",
    "        phi[i*j] = phi[i] * (j-1)\n",
    "        # mobious[i*j] = mobious[i] * mobious[j]\n",
    "    \n",
    "    # for j in range(i, N, i):\n",
    "    #     fact[j].append(i)\n",
    "\n",
    "def getfact(x):\n",
    "    res = defaultdict(int)\n",
    "    while x != 1:\n",
    "        res[pfact[x]] += 1\n",
    "        x //= pfact[x]\n",
    "    return res\n",
    "\n",
    "def factlist(x):\n",
    "    res = [1]\n",
    "    while x != 1:\n",
    "        k = pfact[x]\n",
    "        c = 0\n",
    "        while x % k == 0:\n",
    "            c += 1\n",
    "            x //= k\n",
    "        tmp = []\n",
    "        for i in res:\n",
    "            for j in range(1, c+1):\n",
    "                tmp.append(i * pow(k, j))\n",
    "        res += tmp\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        score = [len(getfact(i)) for i in nums]\n",
    "        left = [0] * n\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            while q and score[q[-1]] < score[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                left[i] = q[-1] + 1\n",
    "            else:\n",
    "                left[i] = 0\n",
    "            q.append(i)\n",
    "        right = [0] * n\n",
    "        q = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while q and score[q[-1]] <= score[i]:\n",
    "                q.pop()\n",
    "            if q:\n",
    "                right[i] = q[-1] - 1\n",
    "            else:\n",
    "                right[i] = n - 1\n",
    "            q.append(i)\n",
    "        nums = [[v, i] for i, v in enumerate(nums)]\n",
    "        nums.sort()\n",
    "        ans = 1\n",
    "        while k:\n",
    "            v, idx = nums.pop()\n",
    "            l, r = left[idx], right[idx]\n",
    "            t1 = idx - l + 1\n",
    "            t2 = r - idx + 1\n",
    "            t = min(k, t1 * t2)\n",
    "            ans *= pow(v, t, int(1e9 + 7))\n",
    "            ans %= int(1e9 + 7)\n",
    "            k -= t\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX = 10**5+5\n",
    "cnt = [0]*MAX\n",
    "mod = 10**9+7\n",
    "for i in range(2,MAX,1):\n",
    "    if not cnt[i]:\n",
    "        for j in range(i,MAX,i):\n",
    "            cnt[j] += 1\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "#         存的是左右两边小于它的点的端点的坐标\n",
    "        L = [0]*n\n",
    "        R = [n-1]*n\n",
    "        for i in range(n):\n",
    "            while stack and cnt[nums[stack[-1]]] < cnt[nums[i]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                L[i] = stack[-1]+1\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and cnt[nums[stack[-1]]] <= cnt[nums[i]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                R[i] = stack[-1]-1\n",
    "            stack.append(i)\n",
    "        ans = 1\n",
    "        list = [[i,(i-L[i]+1)*(R[i]-i+1)] for i in range(n)]\n",
    "        list = sorted(list,key=lambda a: -nums[a[0]])\n",
    "        for v in list:\n",
    "            x = min(k,v[1])\n",
    "            k -= x\n",
    "            ans *=  pow(nums[v[0]],x,mod)\n",
    "            ans %= mod\n",
    "            if k == 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n:int) -> None:\n",
    "        self.n = n\n",
    "        self.primes = [] # 小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    "\n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for i in range(2, int(math.sqrt(x))+1):\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt]\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in range(2, int(math.sqrt(x))+1):\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            yield x, 1\n",
    "\n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "from collections import defaultdict\n",
    "pt = PrimeTable(10 ** 5 + 1)\n",
    "d = defaultdict(list) # num -> len\n",
    "for num in range(1, 10 ** 5 + 1):\n",
    "    d[num] = len(list(pt.prime_factorization(num)))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        fs = []\n",
    "        for num in nums:\n",
    "            fs.append(d[num])\n",
    "        #print(fs)\n",
    "        # 从大到小看，每个数能用多少次？\n",
    "        # 贡献法！\n",
    "        # 单调栈left和right\n",
    "        # 找到左侧第一个大于等于自身的\n",
    "        # 找到右侧第一个大于自身的\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, v in enumerate(fs):\n",
    "            while stack and fs[stack[-1]] < v:\n",
    "                j = stack.pop()\n",
    "                right[j] = i\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and fs[stack[-1]] <= fs[i]:\n",
    "                j = stack.pop()\n",
    "                left[j] = i\n",
    "            stack.append(i)\n",
    "        #print(left)\n",
    "        #print(right)\n",
    "        # 对于i而言，在(left[i], i]和[i, right[i])之间都是可取的\n",
    "        # 要先排序, 从大到小考虑left和right的乘积即可，考虑pow\n",
    "        lst = [(v, i) for i, v in enumerate(nums)]\n",
    "        lst.sort(reverse = True)\n",
    "        idxs = [item[1] for item in lst]\n",
    "        #print(idxs)\n",
    "        cnt = 0\n",
    "        ans = 1\n",
    "        for idx in idxs:\n",
    "            cur = (right[idx] - idx) * (idx - left[idx])\n",
    "            if cur >= k:\n",
    "                #print(nums[idx], k)\n",
    "                ans *= pow(nums[idx], k, MOD)\n",
    "                ans %= MOD\n",
    "                return ans\n",
    "            else:\n",
    "                k -= cur\n",
    "                #print(nums[idx], cur)\n",
    "                ans *= pow(nums[idx], cur, MOD)\n",
    "                ans %= MOD\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9+7\n",
    "mx = 10**5\n",
    "spf = [i for i in range(mx+1)]\n",
    "for i in range(2,int(math.sqrt(mx))+1):\n",
    "    if spf[i]==i:\n",
    "        for j in range(i*i,mx+1,i):\n",
    "            spf[j]=min(spf[j],i)\n",
    "@cache\n",
    "def getScore(x):\n",
    "    facs = set()\n",
    "    while x!=1:\n",
    "        facs.add(spf[x])\n",
    "        x//=spf[x]\n",
    "    return len(facs)\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left,right = [-1]*n,[n]*n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            score = getScore(nums[i])\n",
    "            while stack and score>getScore(nums[stack[-1]]):\n",
    "                right[stack.pop()]=i\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            score = getScore(nums[i])\n",
    "            while stack and score>=getScore(nums[stack[-1]]):\n",
    "                left[stack.pop()]=i\n",
    "            stack.append(i)\n",
    "        res = 1\n",
    "        A = sorted([[v,i] for i,v in enumerate(nums)],reverse=True)\n",
    "        for v,i in A:\n",
    "            cnt = (right[i]-i)*(i-left[i])\n",
    "            take = min(k,cnt)\n",
    "            res = (res*pow(v,take,mod))%mod\n",
    "            k-=take\n",
    "            if not k:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n:int) -> None:\n",
    "        self.n = n\n",
    "        self.primes = []\n",
    "        self.max_div = list(range(n+1))\n",
    "        self.max_div[1] = 1\n",
    "        self.phi = list(range(n+1))\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            if self.max_div[i] == i:\n",
    "                self.primes.append(i)\n",
    "                for j in range(i, n+1, i):\n",
    "                    self.max_div[j] = i\n",
    "                    self.phi[j] = self.phi[j] // i * (i-1)\n",
    "\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.max_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % p == 0: return False\n",
    "        return True\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        if x > self.n:\n",
    "            for p in self.primes:\n",
    "                if p * p > x: break\n",
    "                if x <= self.n: break\n",
    "                if x % p == 0:\n",
    "                    cnt = 0\n",
    "                    while x % p == 0: cnt += 1; x //= p\n",
    "                    yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.max_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            yield x, 1\n",
    "\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, a):\n",
    "        a = self.parent[a]\n",
    "        acopy = a\n",
    "        while a != self.parent[a]:\n",
    "            a = self.parent[a]\n",
    "        while acopy != a:\n",
    "            self.parent[acopy], acopy = a, self.parent[acopy]\n",
    "        return a\n",
    "\n",
    "    def merge(self, a, b):\n",
    "        if self.find(b) != self.find(a):\n",
    "            self.size[self.find(a)] += self.size[self.find(b)]\n",
    "            self.parent[self.find(b)] = self.find(a)\n",
    "\n",
    "    def getSize(self, a):\n",
    "        return self.size[self.find(a)]    \n",
    "\n",
    "pt = PrimeTable(10 ** 5)\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        scores = [sum(1 for p, c in pt.prime_factorization(x)) for x in nums]\n",
    "        ans = 1\n",
    "        n = len(nums)\n",
    "        vis = [0] * n\n",
    "        \n",
    "        uf = UnionFind(n)\n",
    "        tmp = []\n",
    "        for i in sorted(range(n), key=lambda x: (scores[x], -x)):\n",
    "            vis[i] = 1\n",
    "            x = 1\n",
    "            if i and vis[i-1]:\n",
    "                x *= uf.getSize(i-1)+1\n",
    "                uf.merge(i, i-1)\n",
    "            if i + 1 < n and vis[i+1]:\n",
    "                x *= uf.getSize(i+1)+1\n",
    "                uf.merge(i, i+1)\n",
    "            tmp.append((nums[i], x))\n",
    "        tmp.sort(reverse=True)\n",
    "        for v, power in tmp:\n",
    "            if power > k:\n",
    "                ans *= pow(v, k, mod)\n",
    "                ans %= mod\n",
    "                break\n",
    "            else:\n",
    "                ans *= pow(v, power, mod)\n",
    "                ans %= mod\n",
    "                k -= power\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def divide_prime(n: int) -> int:\n",
    "    ans = set()\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        while n % i == 0:\n",
    "            ans.add(i)\n",
    "            n //= i\n",
    "        else:\n",
    "            i += 1\n",
    "    if n != 1:\n",
    "        ans.add(n)\n",
    "    return len(ans)\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        primes = [divide_prime(num) for num in nums]\n",
    "        print(primes)\n",
    "\n",
    "        # 计算贡献度\n",
    "        left, right = list(range(n)), [0] * n\n",
    "        stack = []\n",
    "        for i, p in enumerate(primes):\n",
    "            left[i] -= 1\n",
    "            while stack and primes[stack[-1]] < p:\n",
    "                j = stack.pop()\n",
    "                right[j] = i\n",
    "                left[i] = left[j]\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            j = stack.pop()\n",
    "            right[j] = n\n",
    "        \n",
    "        contribute = []\n",
    "        for i, (l, r) in enumerate(zip(left, right)):\n",
    "            contribute.append((i - l) * (r - i))\n",
    "\n",
    "        ans = 1\n",
    "        for num, c in sorted(zip(nums, contribute), key=lambda x: (-x[0], -x[1])):\n",
    "            if k > c:\n",
    "                ans = ans * pow(num, c, MOD) % MOD\n",
    "                k -= c\n",
    "            else:\n",
    "                ans = ans * pow(num, k, MOD) % MOD\n",
    "                break\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "\n",
    "d = defaultdict(int)\n",
    "def prime_factors(n):\n",
    "    factors = set()\n",
    "    i = 2\n",
    "\n",
    "    while i * i <= n:\n",
    "        if n % i:\n",
    "            i += 1\n",
    "        else:\n",
    "            \n",
    "            while n % i == 0:\n",
    "                n //= i\n",
    "            factors.add(i)\n",
    "    \n",
    "    if n > 1:\n",
    "        factors.add(n)\n",
    "        \n",
    "    return factors\n",
    "for i in range(2, MX):\n",
    "    d[i] = len(prime_factors(i))\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack and d[nums[stack[-1]]] < d[num]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "           \n",
    "            while stack and d[nums[stack[-1]]] <= d[nums[i]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        # print(left, right)\n",
    "        s = sorted(zip(range(n), nums), key=lambda x: -x[1])\n",
    "        ans = 1\n",
    "        for idx, num in s:\n",
    "            \n",
    "            if k:\n",
    "                total = (idx - left[idx]) * (right[idx] - idx)\n",
    "                # print(num, total)\n",
    "                can = min(total, k)\n",
    "                ans = ans * pow(num, can, mod) % mod\n",
    "                k -= can\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "num_sum = 10 ** 5 + 1\n",
    "p_num = [0] * num_sum\n",
    "for i in range(2, num_sum):\n",
    "    if not p_num[i]:\n",
    "        for idx in range(i, num_sum, i):\n",
    "            p_num[idx] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        bignum = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        num_sort = sorted(range(n), reverse=True, key=lambda x: nums[x])\n",
    "        num_score = [p_num[i] for i in nums]\n",
    "        lr = [[0, n - 1] for _ in range(n)]\n",
    "        q = []\n",
    "        for i, v in enumerate(num_score):\n",
    "            while q and q[-1][1] < v:\n",
    "                lr[q.pop()[0]][1] = i - 1\n",
    "            if q:\n",
    "                lr[i][0] = q[-1][0] + 1\n",
    "            q.append((i, v))\n",
    "        res = 1\n",
    "        for i in num_sort:\n",
    "            a, b = i - lr[i][0] + 1, lr[i][1] - i + 1\n",
    "            c = a * b\n",
    "            c = c if c < k else k\n",
    "            # 快速幂计算结果\n",
    "            # res = (res * quick(nums[i], c)) % bignum\n",
    "            res = (res * pow(nums[i], c, bignum)) % bignum\n",
    "            k -= c\n",
    "            if not k:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "MX=10**6+1\n",
    "gPrimes=[0]*MX\n",
    "for i in range(2,MX):\n",
    "    if gPrimes[i]==0:\n",
    "        for j in range(i,MX,i):\n",
    "            gPrimes[j]+=1\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        arr=[]\n",
    "        for i in range(n):\n",
    "            arr.append(gPrimes[nums[i]])\n",
    "        left2=[-1]*n  \n",
    "        st=[]\n",
    "        for i,x in enumerate(arr):\n",
    "            while st and arr[st[-1]]<x:\n",
    "                st.pop()  \n",
    "            if st:\n",
    "                left2[i]=st[-1]\n",
    "            st.append(i)\n",
    "        right2=[n]*n  \n",
    "        st=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and arr[st[-1]]<=arr[i]:\n",
    "                st.pop()  \n",
    "            if st:\n",
    "                right2[i]=st[-1]\n",
    "            st.append(i)\n",
    "        ans=1\n",
    "        for i,x in sorted(enumerate(nums),key=lambda z:-z[1]):\n",
    "            time=(i-left2[i])*(right2[i]-i)\n",
    "            if time<k:ans=(ans*pow(x,time,MOD))%MOD\n",
    "            else:\n",
    "                ans=(ans*pow(x,k,MOD))%MOD\n",
    "                break  \n",
    "            k-=time\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "is_prime = [True] * MX\n",
    "d = defaultdict(int)\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        d[i] += 1\n",
    "        for j in range(i * 2, MX, i):\n",
    "            d[j] += 1\n",
    "            is_prime[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, num in enumerate(nums):\n",
    "            while stack and d[nums[stack[-1]]] < d[num]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "           \n",
    "            while stack and d[nums[stack[-1]]] <= d[nums[i]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        # print(left, right)\n",
    "        s = sorted(zip(range(n), nums), key=lambda x: -x[1])\n",
    "        ans = 1\n",
    "        for idx, num in s:\n",
    "            \n",
    "            if k:\n",
    "                total = (idx - left[idx]) * (right[idx] - idx)\n",
    "                # print(num, total)\n",
    "                can = min(total, k)\n",
    "                ans = ans * pow(num, can, mod) % mod\n",
    "                k -= can\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# def get_primes():\n",
    "#     n = 10**5+ 5\n",
    "#     primes = []\n",
    "#     is_primes = [True] * (n+1)\n",
    "#     for i in range(2,n):\n",
    "#         if is_primes[i]:\n",
    "#             primes.append(i)\n",
    "#         for p in primes:\n",
    "#             if i*p > n: break \n",
    "#             is_primes[i * p] = False\n",
    "#             if i%p==0: break\n",
    "#     return primes\n",
    "\n",
    "# def get_primes():\n",
    "#     n = 10**7\n",
    "#     is_primes = [True] * n\n",
    "#     primes = []\n",
    "#     for i in range(2, n):\n",
    "#         if is_primes[i]:\n",
    "#             primes.append(i)\n",
    "#             for j in range(i*i, n, i):\n",
    "#                 is_primes[j] = False\n",
    "#     return primes\n",
    "\n",
    "# primes = get_primes()\n",
    "\n",
    "MX = 10 ** 6\n",
    "omiga = [0] * MX    # 不同质因子个数, 筛法\n",
    "for i in range(2, MX):\n",
    "    if omiga[i] == 0:\n",
    "        for j in range(i, MX, i):\n",
    "            omiga[j] += 1\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n # 开区间\n",
    "        right = [n] * n # 开区间\n",
    "        st = [] # 单调递减栈,存数组下标\n",
    "        for i in range(n):\n",
    "            while len(st) and omiga[nums[i]] > omiga[nums[st[-1]]]: \n",
    "                right[st.pop()] = i\n",
    "            if len(st):\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 1\n",
    "        for i,a,L,R in sorted(zip(range(n), nums, left, right), key=lambda x:-x[1]):\n",
    "            total = (R - i) * (i - L)\n",
    "            if total > k:\n",
    "                ans *= pow(a, k, MOD)\n",
    "                break\n",
    "            else:\n",
    "                ans *= pow(a, total, MOD)\n",
    "            k -= total\n",
    "        \n",
    "        return ans % MOD\n",
    "        \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10 ** 5 + 1\n",
    "d = defaultdict(int)\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        is_prime[i] = False\n",
    "        d[i] += 1\n",
    "        for j in range(i * 2, MX, i):\n",
    "            is_prime[j] = False\n",
    "            d[j] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack and d[nums[stack[-1]]] < d[nums[i]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and d[nums[stack[-1]]] <= d[nums[i]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        # print(left, right)\n",
    "        ans = 1\n",
    "        for i, num in sorted(zip(range(n), nums), key=lambda x: -x[1]):\n",
    "            tot = (right[i] - i) * (i - left[i])\n",
    "            # print(num, tot)\n",
    "            if not k:\n",
    "                break\n",
    "            if k >= tot:\n",
    "                ans = ans * pow(num, tot, mod) % mod\n",
    "                k -= tot        \n",
    "            else:\n",
    "                ans = ans * pow(num, k, mod) % mod\n",
    "                k = 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        @cache\n",
    "        def prime_score(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            for i in range(2, x + 1):\n",
    "                if i * i > x:\n",
    "                    break\n",
    "                if x % i:\n",
    "                    continue\n",
    "                y = x\n",
    "                while y % i == 0:\n",
    "                    y //= i\n",
    "                return 1 + prime_score(y)\n",
    "            return 1\n",
    "        p = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        cnt = [0] * n\n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while len(stack) > 0 and prime_score(nums[stack[-1]]) < prime_score(x):\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                left[i] += i\n",
    "            else:\n",
    "                left[i] += i - stack[-1] - 1\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            while len(stack) > 0 and prime_score(nums[stack[-1]]) <= prime_score(x):\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                right[i] += n - i - 1\n",
    "            else:\n",
    "                right[i] += stack[-1] - i - 1\n",
    "            stack.append(i)\n",
    "        for i in range(n):\n",
    "            cnt[i] = (left[i] + 1) * (right[i] + 1)\n",
    "        a = [(x, y) for x, y in zip(nums, cnt)]\n",
    "        # print(cnt)\n",
    "        a.sort()\n",
    "        ans = 1\n",
    "        while len(a) != 0 and k > 0:\n",
    "            x, y = a.pop()\n",
    "            y = min(y, k)\n",
    "            # print(x, y)\n",
    "            ans = ans * pow(x, y, p) % p\n",
    "            k -= y\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math, bisect\n",
    "from collections import defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "def sieve_of_sundaram(mx):\n",
    "    if mx < 2:\n",
    "        return []\n",
    "    mx_idx = (mx - 1) // 2\n",
    "    is_prime_idx = [True] * (mx_idx + 1)\n",
    "    for i in range(1, len(is_prime_idx)):\n",
    "        if 2 * i * i + i + i > mx_idx:\n",
    "            break\n",
    "        for j in range(i, len(is_prime_idx)):\n",
    "            if 2 * i * j + i + j > mx_idx:\n",
    "                break\n",
    "            else:\n",
    "                is_prime_idx[2 * i * j + i + j] = False\n",
    "    return [2] + [2 * i + 1 for i, is_prime in enumerate(is_prime_idx) if is_prime and i > 0]\n",
    "\n",
    "PRIMES = sieve_of_sundaram(10 ** 5)\n",
    "PRIME_SCORES = [0] * (10 ** 5 + 1)\n",
    "for prime in PRIMES:\n",
    "    prime_multi = prime\n",
    "    while prime_multi < len(PRIME_SCORES):\n",
    "        PRIME_SCORES[prime_multi] += 1\n",
    "        prime_multi += prime\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "        \n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        # scores = [[PRIME_SCORES[num], i, num] for i, num in enumerate(nums)]\n",
    "        # print(scores)\n",
    "        # group_by_ps = defaultdict(lambda: [-1])\n",
    "        negnum_i_ps_lst = []\n",
    "        for i, num in enumerate(nums):\n",
    "            prime_score = PRIME_SCORES[num]\n",
    "            # group_by_ps[prime_score].append(i)\n",
    "            negnum_i_ps_lst.append([-num, i, prime_score])\n",
    "        # used_indexes = SortedList([len(nums)])\n",
    "        used_index_set = {len(nums)}\n",
    "        \n",
    "        left_sizes = []\n",
    "        stack = [[-1, float(\"inf\")]]  # [[index, ps], ...]\n",
    "        for i, num in enumerate(nums):\n",
    "            # print(\"==========\")\n",
    "            ps = PRIME_SCORES[num]\n",
    "            while stack[-1][1] < ps:\n",
    "                stack.pop()\n",
    "            left_sizes.append(i - stack[-1][0])\n",
    "            stack.append([i, ps])\n",
    "        \n",
    "        right_sizes = [None] * len(nums)\n",
    "        stack = [[len(nums), float(\"inf\")]]  # [[index, ps], ...]\n",
    "        for i, num in reversed(list(enumerate(nums))):\n",
    "            ps = PRIME_SCORES[num]\n",
    "            while stack[-1][1] <= ps:\n",
    "                stack.pop()\n",
    "            right_sizes[i] = stack[-1][0] - i\n",
    "            stack.append([i, ps])\n",
    "        \n",
    "        def get_left_size(num, i, ps):\n",
    "            # indexes = group_by_ps[ps]\n",
    "            # left_bound = indexes[bisect.bisect_left(indexes, i)] - 1\n",
    "            # print(i, left_bound, indexes)\n",
    "            # left_size = i - left_bound\n",
    "            # return left_size\n",
    "            # left_bound = left_neighbors[i]\n",
    "            # return i - left_bound\n",
    "            return left_sizes[i]\n",
    "        \n",
    "        \n",
    "        def get_right_size(num, i, ps):\n",
    "            # used_index = used_indexes[used_indexes.bisect_right(i)]\n",
    "            # right_size = used_index - i\n",
    "            # return right_size\n",
    "            # for j in range(i + 1, len(nums)):\n",
    "            #     if PRIME_SCORES[nums[j]] > ps:\n",
    "            #         right_bound = j\n",
    "            #         break\n",
    "            # else:\n",
    "            #     right_bound = len(nums)\n",
    "            # right_bound = right_neighbors[i]\n",
    "            # return right_bound - i\n",
    "            return right_sizes[i]\n",
    "\n",
    "        def use_index(i):\n",
    "            # used_indexes.add(i)\n",
    "            used_index_set.add(i)\n",
    "\n",
    "        res = 1\n",
    "        for negnum, i, ps in sorted(negnum_i_ps_lst):\n",
    "            num = -negnum\n",
    "            left_size = get_left_size(num, i, ps)\n",
    "            right_size = get_right_size(num, i, ps)\n",
    "            \n",
    "            available_ops = min(k, left_size * right_size)\n",
    "            # print(f\"use {num} at {i} for {available_ops} times (l: {left_size}, r: {right_size})\")\n",
    "            res *= pow(num, available_ops, MOD)\n",
    "            res %= MOD\n",
    "            use_index(i)\n",
    "            k -= available_ops\n",
    "            if k == 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_primes(n):\n",
    "    is_prime = [True] * (n + 1)\n",
    "    primes = []\n",
    "\n",
    "    for p in range(2, n + 1):\n",
    "        if is_prime[p]:\n",
    "            primes.append(p)\n",
    "            for i in range(p * p, n + 1, p):\n",
    "                is_prime[i] = False\n",
    "\n",
    "    return primes\n",
    "\n",
    "def factorize(x, primes):\n",
    "    ret = 0\n",
    "    for i,p in enumerate(primes):\n",
    "        if p * p > x:\n",
    "            break\n",
    "        if x % p == 0:\n",
    "            ret += 1\n",
    "            while x % p == 0:\n",
    "                x //= p\n",
    "    if x > 1:\n",
    "        ret += 1\n",
    "    return ret\n",
    "\n",
    "MOD = 1000000000 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        max_num = max(nums)\n",
    "        primes = get_primes(max_num)\n",
    "        weights  = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            weights.append((factorize(nums[i], primes),-i))\n",
    "        \n",
    "        left = [-1 for _ in range(n)]\n",
    "        right = [-1 for _ in range(n)]\n",
    "        queue = [-1 for _ in range(n)]\n",
    "        top = 0\n",
    "        left[0] = 0\n",
    "        queue[0] = 0\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            while top >=0 and weights[queue[top]] < weights[i]:\n",
    "                top -= 1\n",
    "            \n",
    "            if top == -1:\n",
    "                left[i] = 0\n",
    "            else:\n",
    "                left[i] = queue[top] + 1\n",
    "            \n",
    "            top += 1\n",
    "            queue[top] = i\n",
    "        \n",
    "        queue = [-1 for _ in range(n)]\n",
    "        top = 0\n",
    "        right[n-1] = n-1\n",
    "        queue[0] = n-1\n",
    "        for i in reversed(range(n-1)):\n",
    "            #print(\"x\",queue)\n",
    "            while top >= 0 and weights[queue[top]] < weights[i]:\n",
    "                top -= 1\n",
    "            if top == -1:\n",
    "                right[i] = n-1\n",
    "            else:\n",
    "                right[i] = queue[top] - 1\n",
    "            \n",
    "            top += 1\n",
    "            queue[top] = i\n",
    "\n",
    "        candi = [(nums[i], i) for i in range(n)]\n",
    "        candi = sorted(candi,reverse=True)\n",
    "        \n",
    "        #print(left)\n",
    "        #print(right)\n",
    "        \n",
    "        i = 0\n",
    "        ret = 1\n",
    "        while k > 0:\n",
    "            x, idx = candi[i][0], candi[i][1]\n",
    "            #x, idx = weights[i][0], - weights[i][1]\n",
    "            volume = (idx - left[idx] + 1) * (right[idx] - idx + 1)\n",
    "            if volume >= k:\n",
    "                ret = (ret * pow(x, k, MOD)) % MOD\n",
    "            else:\n",
    "                ret = (ret * pow(x, volume, MOD)) % MOD\n",
    "            k -= volume\n",
    "            i += 1\n",
    "        return ret\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def divide_prime(n: int) -> int:\n",
    "    ans = set()\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        while n % i == 0:\n",
    "            ans.add(i)\n",
    "            n //= i\n",
    "        else:\n",
    "            i += 1\n",
    "    if n != 1:\n",
    "        ans.add(n)\n",
    "    return len(ans)\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        primes = [divide_prime(num) for num in nums]\n",
    "\n",
    "        # 计算贡献度\n",
    "        left, right = list(range(n)), [0] * n\n",
    "        stack = []\n",
    "        for i, p in enumerate(primes):\n",
    "            while stack and primes[stack[-1]] < p:\n",
    "                j = stack.pop()\n",
    "                right[j] = i - 1\n",
    "                left[i] = left[j]\n",
    "            stack.append(i)\n",
    "        while stack:\n",
    "            j = stack.pop()\n",
    "            right[j] = n - 1\n",
    "        \n",
    "        contribute = []\n",
    "        for i, (l, r) in enumerate(zip(left, right)):\n",
    "            contribute.append(1 + (i - l) + (r - i) + (i - l) * (r - i))\n",
    "\n",
    "        ans = 1\n",
    "        for num, c in sorted(zip(nums, contribute), key=lambda x: (-x[0], -x[1])):\n",
    "            if k > c:\n",
    "                ans = ans * pow(num, c, MOD) % MOD\n",
    "                k -= c\n",
    "            else:\n",
    "                ans = ans * pow(num, k, MOD) % MOD\n",
    "                break\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def divide_prime(n: int) -> int:\n",
    "    ans = set()\n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        while n % i == 0:\n",
    "            ans.add(i)\n",
    "            n //= i\n",
    "        else:\n",
    "            i += 1\n",
    "    if n != 1:\n",
    "        ans.add(n)\n",
    "    return len(ans)\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        primes = [divide_prime(num) for num in nums]\n",
    "        print(primes)\n",
    "\n",
    "        # 计算贡献度\n",
    "        left, right = list(range(n)), [n] * n\n",
    "        stack = []\n",
    "        for i, p in enumerate(primes):\n",
    "            left[i] -= 1\n",
    "            while stack and primes[stack[-1]] < p:\n",
    "                j = stack.pop()\n",
    "                right[j] = i\n",
    "                left[i] = left[j]\n",
    "            stack.append(i)\n",
    "        \n",
    "        contribute = []\n",
    "        for i, (l, r) in enumerate(zip(left, right)):\n",
    "            contribute.append((i - l) * (r - i))\n",
    "\n",
    "        ans = 1\n",
    "        for num, c in sorted(zip(nums, contribute), key=lambda x: (-x[0], -x[1])):\n",
    "            if k > c:\n",
    "                ans = ans * pow(num, c, MOD) % MOD\n",
    "                k -= c\n",
    "            else:\n",
    "                ans = ans * pow(num, k, MOD) % MOD\n",
    "                break\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScore(self, nums: List[int], k: int) -> int:\n",
    "        tks = []\n",
    "        pks = [0] * 317\n",
    "        for i in range(2,317):\n",
    "            if pks[i] == 0:\n",
    "                tks.append(i)\n",
    "                ni = i + i\n",
    "                while ni < 317:\n",
    "                    pks[ni] = 1\n",
    "                    ni += i\n",
    "        n = len(nums)\n",
    "        def g(x):\n",
    "            if x == 1: return 0\n",
    "            tep = 0\n",
    "            for i in tks:\n",
    "                if x % i == 0:\n",
    "                    tep += 1\n",
    "                    while x % i == 0:\n",
    "                        x //= i\n",
    "                    if x == 1: return tep\n",
    "            return tep + 1\n",
    "                \n",
    "        has = [[0,n-1] for i in range(n)]\n",
    "        dq = [[100001,n]]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            v = g(nums[i])\n",
    "            while dq[-1][0] <= v:\n",
    "                a,b = dq.pop()\n",
    "                has[b][0] = i+1\n",
    "            has[i][1] = dq[-1][1] - 1\n",
    "            dq.append([v,i])\n",
    "        lis = sorted(range(n), key = lambda x:[nums[x],-x])\n",
    "        res = 1\n",
    "        # print(has, lis, [g(i) for i in nums])\n",
    "        while k:\n",
    "            a = lis.pop()\n",
    "            v = nums[a]\n",
    "            kv = (has[a][1] - a + 1) * (a - has[a][0] + 1)\n",
    "            if k > kv:\n",
    "                k -= kv\n",
    "                res = (res * pow(v,kv,1000000007)) % 1000000007\n",
    "                \n",
    "            else:\n",
    "                res = (res * pow(v,k,1000000007)) % 1000000007\n",
    "                \n",
    "                break\n",
    "        return res % 1000000007"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
